1. 两数之和

先考虑暴力枚举：把数组中的不同位置两两配对，遇到和等于目标值的数对，就返回它们的索引。

Python 代码如下：

Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    n=len(nums)
    for i in range(n):
        for j in range(i+1,n):
            if nums[i]+nums[j]==target:
                return [i,j]

C++ 代码如下：

C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                return vector<int>{i, j};
            }
        }
    }
    return vector<int>();
}
};

双层循环的时间复杂度为 O(n2n^2)。换个角度看，既然要找 x+y=targetx+y=target，那么遍历到 x 时，需要找的另一个数就是 y=target−xy=target-x。

如果每次都遍历数组查找 y，仍然会产生大量重复查找。可以用哈希表记录已经遍历过的数：键是数值，值是索引。遇到 x 时，先检查表中是否存在对应的 y；存在就返回两个索引，不存在就把当前数和索引存入表中。这样只需遍历一次数组，平均时间复杂度为 O(n)。

Python 代码如下：

Python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        hs=dict()
        for i in range(n):
            y=target-nums[i]
            if y in hs:
                return [i,hs[y]]
            hs[nums[i]]=i

C++ 代码如下：

C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hs;
        for (int i = 0; i < nums.size(); i++) {
            int y = target - nums[i];
            if (hs.count(y))
                return vector<int>{i, hs[y]};
            hs[nums[i]] = i;
        }
        return vector<int>{};
    }
};
谢谢你读到这里。 ✧