力扣——哈希——1.两数之和

题目

解法

1、暴力

初始

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

错误

修改后

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

2、哈希

思路

使用哈希表，遍历map表

查询标准值减去当前正在查的值的差在哈希表中是否存在，如果存在，说明这一对就是要找的值。直接返回即可

如果不存在，因为这是数组内的第i个值，所以哈希表的值就是i，索引是具体的值，如hashtable[nums[i]]=i;，里面的i是在查看nums数组内的第i个值

find——>ite->first—>键值；ite->second—>索引

例子

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int len=nums.size();
        unordered_map<int,int> ans;
        for(int i=0;i<len;++i)
        {
            //寻找补数是否在哈希表内
            auto ite=ans.find(target-nums[i]);
            //如果哈希表内没到结尾就找到了这个补数，那这个补数和当前的i就是结果，直接返回即可
            if(ite!=ans.end())
            {
                //返回
                return {ite->second,i};
            }
            //如果哈希表没找到，原表的第i个位置的值为nums[i]，则将这个值作为下标放入ans的位置，值为i
            ans[nums[i]]=i;
        }
        //如果没找到，返回空值
        return {};
    }
};