两数之和 [ leetcode ]

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

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

以上是原题

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

先来看常规思路：

　　无脑循环法：

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

     public int[] twoSum(int[] nums, int target) {

         for (int i = 0; i < nums.length - 1; i++) {

             for (int j = i + 1; j < nums.length; j++) {

                 if (target == nums[i] + nums[j]) {

                     return new int[]{i, j};

                 }

             }

         }

         return null;

     }

　　时间复杂度：O(n²)　　

　　哈希法：

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

     public int[] twoSum(int[] nums, int target) {

         Map<Integer, Integer> map = new HashMap<>();

         for (int i = 0; i < nums.length; i++) {

             map.put(nums[i], i);

         }

         for (int i = 0; i < nums.length; i++) {

             int c = target - nums[i];

             Integer t = map.get(c);

             if (t != null && t != i) { // t != i 排除同一个元素被利用两次的情况

                 return new int[]{map.get(target - nums[i]), i};

             }

         }

         return null;

     }

　　先将数组元素与其下标的对应关系存入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).

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

     public int[] twoSum(int[] nums, int target) {

         Map<Integer, Integer> map = new HashMap<>();

         for (int i = 0; i < nums.length; i++) {

             int c = target - nums[i];

             Integer t = map.get(c);

             if(t != null) {

                 return new int[]{map.get(target - nums[i]), i};

             }

             map.put(nums[i], i);

         }

         return null;

     }

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

巴特西

两数之和 [ leetcode ]

最新文章

热门文章