中文版本

题目

难度：简单

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 > [0, 1]

解题思路

（1）暴力法：

遍历每个元素 xx，并查找是否存在一个值与 target - xtarget−x 相等的目标元素。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for idx_1 in range(len(nums)):
            minus = target - nums[idx_1]
            for idx_2 in range(len(nums)):
                if idx_2 == idx_1:
                    continue
                if nums[idx_2] == minus:
                    return [idx_1, idx_2]

时间复杂度：O(n^2)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)的时间。因此时间复杂度为 O(n^2)。

空间复杂度：O(1)。

（2）哈希表法：

使用暴力法后，感觉时间复杂度过高。思路陷入瓶颈，参考了解题思路后发现可以用哈希表来降低时间复杂度。于是重写代码。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = dict()

        # init the dict
        for idx in range(len(nums)):
            num = nums[idx]
            num_dict[num] = idx

        # search result in the dict
        for idx in range(len(nums)):
            minus = target - nums[idx]
            if num_dict.get(minus) != None and num_dict.get(minus) != idx:
                return [num_dict.get(minus), idx]

复杂度分析：

时间复杂度：O(n)， 我们把包含有 nn 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1)，所以时间复杂度为O(n)。

空间复杂度：O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。

写完后发现其实是“两遍哈希表法”，还存在一种更优的方法：“一遍哈希表法”，以下摘抄自官方解析：

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = dict()
        for idx in range(len(nums)):
            num = nums[idx]
            if num_dict.get(target - num) != None:
                return [num_dict[target - num], idx]
            num_dict[num] = idx

Java Version：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

Go Version：

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for idx, num := range nums {
        minus := target - num
        n, ok := m[minus]
        if ok == true{
            return []int{n, idx}
        }
        m[num] = idx
    }
    return nil
}

总结

通过以空间换取速度的方式，我们可以将查找时间从 O(n) 降低到 O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。

English Version（TODO：）

title

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].