1.由两数之和找加数

发表于 | 分类于 | 阅读次数

两数之和

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

1、双重循环

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
        public int[] twoSum(int[] nums, int target) {
            int size = nums.length;
            for (int i = 0; i < size; i++) {
                for (int j = i + 1; j < size; j++) {
                    if (nums[j] == target - nums[i]) {
                        return new int[]{i, j};
                    }
                }
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    }

时间复杂度：O(n^2)，空间复杂度：O(1)。

2、两遍哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int size = nums.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < size; i++) {
            map.put(nums[i], i);
        }
        // 这里不遍历map,是根据nums[i]去查找map中符合的key
        for (int i = 0; i < size; i++) {
            int leftValue = target - nums[i];
            //注意不能重复利用同一元素
            if (map.containsKey(leftValue) && map.get(leftValue) != i) {
                return new int[]{i, map.get(leftValue)};
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

时间复杂度O(n)，空间复杂度：O(n)。

将数组值作为key,下标作为value。使用map.containsKey()方法。

会有这样的疑惑：相同的值，put进map时会覆盖。但这里其实不影响输出被覆盖的值的下标。因为第二个for循环，是以数组的nums[i]为依据去查找map。

如int[] nums=new int[]{6,2,4,2,5};
int target=4;
map中(2,3)会把(2,1)覆盖掉。但当第二个for循环i=1时，会在map中查到(2,3)，输出{1,3}。

3、一遍哈希表

可对方法2进行优化，一遍遍历，先查看map中是否有当前元素对应的目标元素，若无：将当前元素put进map。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int size = nums.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < size; i++) {
            int leftValue = target - nums[i];
            if (map.containsKey(leftValue) && map.get(leftValue) != i) {
                // 注意顺序
                return new int[]{map.get(leftValue), i};
            }
            // 先查找，后put
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

时间复杂度：O(n)，空间复杂度O(n)。

题目：力扣No.1-两数之和