【LeetCode-数组】两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例：

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

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

题目链接：https://leetcode-cn.com/problems/two-sum

思路1

遍历两遍数组，第一遍遍历时固定一个数字x，在第二遍遍历时寻找另一个数字target-x，要注意x和target-x的下标不能相同。代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        if(nums.empty())
            return ans;

        for(int i=0; i<nums.size(); i++){
            int idx = hasAnotherNum(target-nums[i], nums, i);
            if(idx!=-1 && idx!=i){
                ans.push_back(i);
                ans.push_back(idx);
                return ans;
            }
        }
        return ans;
    }

    int hasAnotherNum(int num, vector<int> nums, int curNumIdx){
        for(int i=0; i<nums.size(); i++){
            if(i!=curNumIdx && nums[i]==num)
                return i;
        }
        return -1;
    }
};

时间复杂度O(n^2)
因为遍历每一个数字的时候，还需要遍历一遍（n次）去寻找另一个数字，共n个数字，所以时间复杂度为O(n^2).
空间复杂度O(1)
算法运行需要的辅助空间和输入规模无关，空间复杂度为O(1).

思路2

思路2是对思路1在时间复杂度上的优化。思路1比较慢的原因是，每次要用一个循环来查找元素。查找元素比较快的方法是哈希表，哈希表查找元素的时间复杂度为O(1)，可以大大地降低查找耗时。这里使用c++的map来实现哈希表。代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        if(nums.empty())
            return ans;

        map<int, int> hashTabel;
        for(int i=0; i<nums.size(); i++)
            hashTabel[nums[i]] = i;    // 建立哈希表
        
        for(int i=0; i<nums.size(); i++){
            int complement = target-nums[i];
            if(hashTabel.find(complement)!=hashTabel.end() && hashTabel[complement]!=i){
                ans.push_back(i);
                ans.push_back(hashTabel[complement]);
                return ans;
            }
        }
        return ans;
    }
};

时间复杂度为O(n)
两个并列的循环，时间复杂度为O(n).
空间复杂度O(n)
哈希表占用的空间随输入规模的上升线性增长，所以空间复杂度为O(n).

思路3

还可以对思路2进一步优化。思路二使用了两个并列的循环，其中第一个循环用来建立哈希表。其实，可以边判断边建立哈希表，也就是使用1个循环。代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        if(nums.empty())
            return ans;

        map<int, int> hashTabel;

        for(int i=0; i<nums.size(); i++){
            if(hashTabel.find(target-nums[i])!=hashTabel.end()){
                ans.push_back(hashTabel[target-nums[i]]);   //先放hashTabel[target-nums[i]]
                ans.push_back(i);
                return ans;
            }
            hashTabel[nums[i]] = i;
        }
        return ans;
    }
};

需要注意的是，在ans中要先放hashTabel[target-nums[i]]，后放i。因为hashTabel[target-nums[i]]更小。
时间复杂度和空间复杂度与思路2相同。

总结

在查找时可以使用哈希表替代循环来降低时间复杂度，加快速度。