1 - 两数之和

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

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

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

解题方法

暴力法

遍历数组，依次判断 arr[0]+arr[1]、arr[0]+arr[2] ...、arr[1]+arr[2]、arr[1]+arr[3] ...、arr[2]+arr[3]、arr[2]+arr[4] ...

因为需要遍历 N×(N-1)/2 次循环，所以时间复杂度为 O(N²)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    // Brute Force
    // @爱学习的饲养员
    // N is the size of nums
    // Time Complexity: O(N^2)
    // Space Complexity: O(1)
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = nums[i] + nums[j];
                if (sum == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
}

哈希表

  1. 赋值 map，以 nums 数组的值为 key，其索引为 value
  2. 遍历数组，判断 map 是否包含 target - arr[索引] 的 key。因为数组中同一个元素在答案里不能重复出现，所以还需要保证 map.get(target - arr[索引]) != 当前索引值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    // HashMap
    // @爱学习的饲养员
    // N is the size of nums
    // Time Complexity: O(N)
    // Space Complexity: O(N)
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int j = 0; j < nums.length; j++) {
            int diff = target - nums[j];
            if (map.containsKey(diff) && map.get(diff) != j) {
                result[0] = j;
                result[1] = map.get(diff);
                return result;
            }
        }
        return result;
    }
}