1.题目

2.思路

法一：暴力枚举，不解释。

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

法二：哈希

题目说明了只有一种情况，所以给定的每个数字是不同的。
可使用unordered_map哈希表，每次查找nums[i]时就查找哈希表中的key值为target-nums[i]键值对是否存在——如果存在则可以直接返回两个结果；注意如果不存在的话不代表没结果，而是将{nums[i],i}插入到哈希表中，注意可以使用pair容器。

虽然for循环内找到一组时会返回值，但是外面也要注意不要漏了return {}——如果没有找到一组也要返回值。

时间复杂度为$O(n)$。

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/113697604