跳转至

1 两数之和

leetcode

强烈建议本题和167 两数之和 II - 输入有序数组对比做

暴力版

遍历每个元素,枚举数组该元素后的每个元素,判断nums[i] + nums[j] 是否等于target

  • 如果是,返回{i, j}
  • 如果遍历整个数组都没有找到{i,j},返回空数组
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

时间复杂度:\(O(n^2)\)

空间复杂度:\(O(1)\)

优化版

在暴力版中,我们发现:定位元素nums[i]后,寻找元素nums[j]花费了\(O(n)\)的时间复杂度

因此可以使用哈希表进行优化,哈希表查找元素效率为\(O(1)\)

使用哈希表优化思路:

  • 我们判断某个元素的值是否存在,因此该元素的值作为哈希表的key值
  • 题目要求返回元素的下标,因此该元素的下标作为哈希表的value值

最简单的想法

遍历一遍数组,将每个元素加入到哈希表中

然后再遍历一遍数组,定位元素nums[i]时,通过哈希表查询是否存在target - nums[i],如果存在返回下标

需要注意的是,题目要求不能使用同一元素多次,也就是说nums[i] != hashMap[target - nums[i]]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hashMap;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            hashMap.insert({nums[i],i});
        }
        for(int i = 0; i < n; i++){
            int num = target - nums[i];
            if(hashMap.count(num) && hashMap[num] != i){
                int j = hashMap[num];
                return {i, j};
            }
        }
        return {};
    }
};

以上做法使用了两次for(int i = 0; i < n; i++),我们能够在一次循环中完成整个算法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hashMap;
        int n = nums.size();
        for(int i = 0; i < n; i++){           
            int num = target - nums[i];
            if(hashMap.count(num)){
                int j = hashMap[num];
                return {i, j};
            }
            // 为了不使用当前元素,判断完之后再插入
            hashMap.insert({nums[i],i});
        }
        return {};
    }
};

注意:不需要初始化往hashMap添0,因为题目限定了两个整数的和

时间复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

通用框架

可惜,本节不是告诉你有多的解法,而是告诉你这种解法为什么无效

你可能会先排序,然后利用双指针找到和为目标值的两个元素,找到后返回数组下标left和right

一切都是那么完美,然而你发现没有AC,这是因为你返回的是排序后的数组下标,而题目求的是原来的数组下标

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1;
        // 不能使用两次相同元素,所以left == right没意义
        while(left < right){
            if(nums[left] + nums[right] == target){
                return {left, right};
            }else if(nums[left] + nums[right] < target){
                left++;
            }else if(nums[left] + nums[right] > target){
                right--;
            }
        }
        return {};
    }
};

你意识到了这一点,然后用哈希表记录原来元素对应的位置

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++){
            hashMap[nums[i]] = i;
        }
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1;
        // 不能使用两次相同元素,所以left == right没意义
        while(left < right){
            if(nums[left] + nums[right] == target){
                return {hashMap[nums[left]], hashMap[nums[right]]};
            }else if(nums[left] + nums[right] < target){
                left++;
            }else if(nums[left] + nums[right] > target){
                right--;
            }
        }
        return {};
    }
};

在样例[3,3]上面栽跟头了,因为数组可能出现多个值,哈希表unordered_map<int,int>无法记录一个值对应的多个索引。

如果要坚持下去,我们只能给哈希表加点料了。为了解决哈希表无法记录多个索引,我们把value由int改为容器类型,选择哪个容器大有讲究,因为我们返回的时候需要按从小到大的顺序返回,然而初始化哈希表的时候容器的索引也是从小到大添加的,因此符合FIFO,为此我们选择队列

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, queue<int>> hashMap;
        for (int i = 0; i < nums.size(); i++) {
            hashMap[nums[i]].push(i);
        }
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1;
        // 不能使用两次相同元素,所以left == right没意义
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                int idx1 = hashMap[nums[left]].front();
                hashMap[nums[left]].pop();
                int idx2 = hashMap[nums[right]].front();
                hashMap[nums[right]].pop();
                return {idx1, idx2};
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else if (nums[left] + nums[right] > target) {
                right--;
            }
        }
        return {};
    }
};

这次AC了,但是为了使用通用框架,感觉有点麻烦了,建议还是使用未排序双指针法

本次尝试告诉了我们两个tips:

  1. 排序后再双指针适用于求满足nSum的值,而不是下标
  2. 如果需要求数组下标,那么不能排序

相比之下,167 两数之和 II - 输入有序数组给出了求的是排序之后的下标,那么就可以使用通用框架。