LeetCode-Q1-两数之和

发表于 更新于 分类于 阅读次数： Changyan： 本文字数： 2.1k 阅读时长 ≈ 3 分钟

Q1.两数之和

问题描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示:

  • $2 <= nums.length <= 10^{4}$
  • $-10^9 <= nums[i] <= 10^9$
  • $-10^9 <= target <= 10^9$
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 $O(n^2)$ 的算法吗？

思路

  • 粗暴的方法是双层遍历，时间复杂度是$O(n^2)$,空间复杂度是$O(1)$。对数组中每个元素遍历整个数组，判断是否存在目标值满足要求。
  • 我们利用辅助空间来优化查找第二个整数的速度，使用HashMap可以将查找的速度优化到$O(1)$.
    1. 即可以先通过一趟遍历将所有数放入hashmap,再通过一趟遍历查找每个元素(基数)的对应值。
    2. 时间复杂度：$O(n)$
    3. 空间复杂度：$O(n)$
    4. 进一步优化: 考虑符合条件的结果对a,b。在上面的思路中，实际上是经过了两次查询(基数a查询b,基数b查询a)。我们可以更进一步优化,在一遍遍历中，只查询前面的元素。
      1. 对于满足条件的结果对a,b(数组顺序a在b前面).基数是b的时候可以保证在hashmap中已经有a,可以直接返回。
      2. 对于不符合条件的x,返回还是找不到。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 两数之和.
 * <pre>
 *  利用缓存map的key,存储目标值，实现O(1)的判断速度.
 * </pre>
 * @tag 遍历
 * @tag 辅助空间
 */
public class Solution1 implements TwoSumSolution{
    public int[] twoSum(int[] nums, int target) {
        // 用于暂存某个数的待匹配数据
        Map<Integer,Integer> dic = new HashMap<>();
        for (int i=0;i<nums.length;i++){
            // 目标数的待匹配数值
            Integer pair = target - nums[i];
            if(dic.containsKey(pair)){
                // 找到就返回，防止重复查找
                return new int[]{dic.get(pair),i};
            }
            dic.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
  • 这道题还可以使用先排序然后通过左右指针的方式遍历数组。同样是一趟遍历返回数字组合。注意，原数组不是有序数组，要先遍历一次，缓存下数字和索引的关系。
    • 时间复杂度：$O(nlogn)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution2 implements TwoSumSolution {
    public int[] twoSum(int[] nums, int target) {
        // 保存数字和索引的映射关系
        Map<Integer,Integer> indexMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            indexMap.put(nums[i],i);
        }
        // 重拍序
        Arrays.sort(nums);
        // 左右指针
        int left= 0;
        int right = nums.length-1;
        while(left<right){ // 终止条件
            if(nums[left] + nums[right]> target){
                right--;
            }else if(nums[left] + nums[right]< target) {
                left++;
            }else{
                if (nums[left] + nums[right] == target) {
                    return new int[]{indexMap.get(nums[left]),
                            indexMap.get(nums[right])};
                }
            }
        }
        return new int[]{};
    }
}