Leetcode-两数之和

1.暴力枚举

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

新知识：

return {i，j}是一种初始化列表的语法，用于返回一个由两个元素组成的容器。具体返回的类型取决于函数的返回类型。也就是说函数返回时自动赋予类型。

时间复杂度：O（n^2）

2.哈希表

nums={6，3，8，2，1}   target = 8

一层循环：遍历到6时，哈希表无元素，直接插入哈希表；

遍历到3时，向哈希表中查找 target - 3 (= 5)，此时表中只有6，没有找到，也把3插入哈希表；

遍历到8时，向哈希表查找0，没有找到，把8插入哈希表

遍历到2时，向哈希表查找6，找到了！此时返回一个数组{6的哈希值（下标），2的下标}即可

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int>m;
        m.insert(map<int,int>::value_type(nums[0],0));
        for(int i=1;i<nums.size();i++){
            if(m.count(target-nums[i])>0){
                return {m[target-nums[i]],i};
            }
            else{
                m.insert({nums[i],i});
            }
        }
        return{0,0};
    }
};

m.insert(map<int,int>::value_type(nums[0],0))通过显式构造一个 std::pair 来实现插入，是C++中一种较为传统的写法。可以简化为 m.insert({nums[i], i});

else{
    m[nums[i]]=i;//直接赋值的方式也可以实现插入，因为map会为不存在的元素自动创建键值对
}