Leetcode0001-两数之和

发表于 | 分类于 ，

Two Sum

难度：简单

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

1
2
3
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1
2
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

1
2
Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 2 <= nums.length <= 103
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

解决方案

方案一：暴力解决

两层循环，第一层循环从第 i 个与元素开始（1 <= i <= 数组长度），第二层循环从第 j 个元素开始（i + 1 <= j <= 数组长度），每次判断第 i 个元素和第 j 个元素之和是否等于目标值，若等于则找到对应元素，返回即可。

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

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] twoSum(int[] nums, int target) {
    int num;
    for(int i=0, len = nums.length; i<len; i++) {
        num = nums[i];
        if(num >= target) {
            continue;
        }
        for(int j=i+1; j<len; j++) {
            if(num + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}

方案二：利用 Map 优化时间复杂度

利用 map 中查找元素时间复杂度为 O(1) 的特性，将元素及对应的下标索引存储到 map 中去。依次扫描数组中每一个元素，然后在 map 中查找是否存在目标值减去当前元素值的元素 ，如果找到了，直接返回 2 个数字的下标即可；如果找不到，就把这个数字存入 map 中，继续向后扫描，并重复上述操作，直达找到结果。

时间复杂度 O(n)

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
private int[] towSum2(int[] nums, int target) {
    int len = nums.length;
    Map<Integer, Integer> map = new HashMap<>(len);
    for(int i=0; i<len; i++) {
        int complement = target - nums[i];
        if(map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        } else {
            map.put(nums[i], i);
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}