1. 两数之和

这个题我们可以简单的想到暴力枚举的方案,让所有的数字两两组合,如果等于目标值.就返回对应的索引.

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++代码如下:

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($n^2$).我们就可以换个角度看能不能优化一下.既然我们要找$x+y=target$.那遍历数组,就是要找$y=target-x$.

但是如果使用查找算法,去查找每一个y,那么时间复杂度也很高,这时候我们就可以使用哈希表了.每遍历一个元素x,如果哈希表里有对应的y,就直接返回两个数的索引,如果没有,就把这个数作为键,把索引作为值存进哈希表.那么时间复杂度就可以优化到O(n)的一个时间复杂度.

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++代码如下：

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