[哈希表]leetcode1：两数之和(easy)

156 阅读 0 评论 103 点赞

我是靠谱客的博主繁荣含羞草，这篇文章主要介绍[哈希表]leetcode1：两数之和(easy)，现在分享给大家，希望可以做个参考。

题目：
在这里插入图片描述
题目链接：https://leetcode-cn.com/problems/two-sum/
x+y=target，每次再插入x前，先查询x的补数y（target-x），再进行插入x。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    // 题解1：双重for暴力，时间复杂度O(n^2)，空间复杂度O(1)
    vector<int> twoSum_1(vector<int>& nums, int target) {
        vector<int> res;
        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)
                {
                    res.push_back(i),res.push_back(j);
                    return res;
                }
        return res;
    }

    // 题解2：hashmap，为了保证x不会自己与自己匹配，我们可以先查询target-x是否存在，再进行插入x
    vector<int> twoSum(vector<int>& nums,int target)
    {
       unordered_map<int,int> mp;
       for(int i=0;i<nums.size();++i)
       {
           // 先查询再插入
           if(mp.find(target-nums[i])!=mp.end())
                return {i,mp[target-nums[i]]};
            mp[nums[i]]=i;
       }
       return {};
    }
};