0001.Two Sum

Description

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

(en)https://leetcode.com/problems/two-sum
(中文)https://leetcode-cn.com/problems/two-sum

Example:

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

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

1
2
3
4

Solutions

Solution 1

对于这样的题目，最容易想到的是brute-force暴力解法, 直接两重循环进行迭代.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[j] == target-nums[i])
                    return new int[] {i, j};
            }
        }
        // Returns null if solution not found.
        return null;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析(Complexity Analysising):

时间复杂度(Time complexity): $O(n^2)$
空间复杂度(Space complexity): $O(1)$

Solution 2

暴力解法虽然可行，但是时间复杂度为 $O(n^2)$ , 考虑进行优化，首先想到是可以以空间换时间:

思路

如果能够把给定数组的数，用某种数据结构将每个数的数值以及对应的索引(index)保存起来，则只需要用一次遍历查找 target - nums[i]是否存在于该数据结构中，且非nums[i]即可。

使用hashMap保存数组中每个数以及对应的索引

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int remain = target - map.get(nums[i]);
            if (map.containsKey(remain) && map.get(remain) != i)
                return new int[] {i, map.get(remain)};
        }
        // returns null if solution not found.
        reutrn null;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析(Complexity Analysising):

时间复杂度(Time complexity): $O(n)$
空间复杂度(Space complexity): $O(n)$

Solution 3

想法

年轻的我，本以为上面的这种解法已经是最优的了，但是看完讨论区之后，才焕然大悟，它还可以进行优化: 仔细看的话，上面的HashMap算法访问了nums数组两遍，而接下来，从leetcode上学习到的优化方法就是将nums数组的访问从两遍降到一遍.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int remain = target - nums[i];
            if (map.containsKey(remain))
                return new int[] {map.get(remain), i};
            map.put(nums[i], i);
        }
        return null;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

注意

由于map中保存的肯定是索引i之前的数，因此不需要判断map.get(remain) != i.

复杂度分析(Complexity Analysising):

时间复杂度(Time complexity): O(n)
空间复杂度(Space complexity): O(n)

Summary

对于能够快速使用brute-force暴力解法解决的问题，考虑优化时，首先考虑能够减少循环的嵌套，其次是考虑减少数组的访问次数、元素比较次数、元素交换次数等。

# 0001.Two Sum

# Description

# Solutions

# Solution 1

# Solution 2

# Solution 3