两数之和 [ leetcode ]

ゝ一纸荒年。 2021-10-01 02:10 271阅读 0赞

原题地址：https://leetcode-cn.com/articles/two-sum/

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

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

--------------------

以上是原题

--------------------

本题得出正确答案非常简单，但显然题目的意图不仅仅是得到答案，而是以更好的方式得出答案。

先来看常规思路：

**无脑循环法：**

两层循环嵌套，依次相加数组元素，和等于目标值，则返回两个循环的下标，代码如下：

1     public int[] twoSum(int[] nums, int target) {
     2         for (int i = 0; i < nums.length - 1; i++) {
     3             for (int j = i + 1; j < nums.length; j++) {
     4                 if (target == nums[i] + nums[j]) {
     5                     return new int[]{i, j};
     6                 }
     7             }
     8         }
     9         return null;
    10     }

时间复杂度：O(n2)

**哈希法：**

利用哈希表存储数组元素与下标的对应关系，通过一定的空间代价来换取更少的时间消耗，给出代码：

1     public int[] twoSum(int[] nums, int target) {
     2         Map<Integer, Integer> map = new HashMap<>();
     3         for (int i = 0; i < nums.length; i++) {
     4             map.put(nums[i], i);
     5         }
     6         for (int i = 0; i < nums.length; i++) {
     7             int c = target - nums[i];
     8             Integer t = map.get(c);
     9             if (t != null && t != i) { // t != i 排除同一个元素被利用两次的情况
    10                 return new int[]{map.get(target - nums[i]), i};
    11             }
    12         }
    13         return null;
    14     }

先将数组元素与其下标的对应关系存入hashmap中，在遍历数组元素，用目标值减去数组元素，如果在hashmap中能通过差值取到对应的元素，则说明该元素与差值为题目中要求得的结果。为什么要判断 （t != i）呢？这里有一种特殊情况，例如 \[2, 3, 1\]的数组，target=4，那么map中的值为\{2 : 0, 3 :1, 1 : 2\}， 在第一次循环中 nums\[0\] = 2， target - nums\[0\] = 2， map.get(nums\[0\]) 能取到对应的值2，返回结果\[ map.get(nums\[0\]), nums\[0\] \] 也就是\[0, 0\]，正确的结果应为\[1, 2\].

采用hash法，时间复杂度为O(n).

改解法可进一步优化为一次循环：

1     public int[] twoSum(int[] nums, int target) {
     2         Map<Integer, Integer> map = new HashMap<>();
     3         for (int i = 0; i < nums.length; i++) {
     4             int c = target - nums[i];
     5             Integer t = map.get(c);
     6             if(t != null) {
     7                 return new int[]{map.get(target - nums[i]), i};
     8             }
     9             map.put(nums[i], i);
    10         }
    11         return null;
    12     }

这里重点要注意第9行的map.put(nums\[i\], i) 要写在map.get(c)语句之后，原因与上段代码判断（t != i）相同。

转载于:https://www.cnblogs.com/zfLee/p/9354132.html