题目

中文

https://leetcode-cn.com/problems/two-sum/

英文

题解

第一次

个人思考

暴力枚举一定可行，还是想不到其他方向。
看题解有人说 哈希表（因为哈希的查找时间复杂度O（1））。 码住，之后做。

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

第二次

哈希表解决
a,b—>a+b=target
for each a:check (target-a) exists in nums
对应每一个a 查询target-a是否在哈希表里面。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};