LeetCode第一题：两数之和
题目描述题目分析题目解答思路一：双重for循环（1）代码（2）提交结果思路二：hashmap键值对一次遍历（1）代码（2）提交结果思考总结

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

这一题我想大部分人第一思路应该都是双重for循环来遍历数组。这也是我的第一思路，遍历两次数组，当外循环下标和内循环下标对应的两个数相加为target时，退出循环。这时候我们就找出了这两个数，但我们需要考虑到题目条件不能重复利用数组中同样的元素。
其实我看到这个条件的时候想了半天，
这个条件的意思是：两个数据的值不能相同

例如：nums =[1,2,2,3] target = 4
只能返回 [0,3] 而不是 [1,2]

还是：两个数据的下标不能相同

例如：nums =[1,2,3] target = 4
只能返回 [0,2] 而不是 [1,1]

又或者两者都有（好像有点钻牛角尖）

时间复杂度：O(n^2)

 

  1.  1  class Solution {
  2.  2      public int[] twoSum(int[] nums, int target) {
  3.  3          int length = nums.length;
  4.  4          for (int i = 0; i < length; i++) {
  5.  5              for (int j = 0; j < length; j++) {
  6.  6                  //这里把条件当做不能使用相同的下标元素
  7.  7                  if (j != i && nums[i]+nums[j] == target)
  8.  8                      return new int[]{i,j};
  9.  9              }
  10. 10          }
  11. 11          return new int[]{};
  12. 12      }
  13. 13 }

 

 

 

 

 

将nums[i]作为key，i作为value。
hashmap搜索算法时间复杂度为O(1)
整个算法在最坏的情况下将数组nums中所有值遍历完也就是O(n)
所以这种解法的时间复杂度：O(n) 

  1.  1 class Solution {
  2.  2     public int[] twoSum(int[] nums, int target) {
  3.  3         int length = nums.length;
  4.  4         HashMap<Integer,Integer> hashMap = new HashMap();
  5.  5         for (int i = 0; i < length; i++)
  6.  6             //如果hashmap中有这个key则直接返回
  7.  7             //如果没有，则存入hashmap之中
  8.  8             if (hashMap.containsKey(target - nums[i]))
  9.  9                 return new int[]{i,hashMap.get(target-nums[i])};
  10. 10             else
  11. 11                 hashMap.put(nums[i],i);
  12. 12         return new int[]{};
  13. 13     }
  14. 14 }

 

 

 

根据这题的两种解法就可以看出，不同的算法会有不同的效率，所以我们在编程的时候，不要仅仅局限于解出这个题目，而是要在解决问题的基础上想办法去优化你的算法，使之效率更高。

 

版权声明：本文为jplusztx原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/jplusztx/p/jplusztx.html