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[1]+arr[3] ...

因为需要遍历Nb*Nb次循环，所以时间复杂度为O(N^2)

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;
    }
}