leetcode1.两数之和_class solution { public: vector twosum(vector

给定一个整数数组 nums 和一个整数目标值 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};

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：思路：
利用map构建hash表，target-num[I]作为target值，I作为value值,

//利用哈希表
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> hash;
        for(int i=0;i<nums.size();i++)
        {
            map<int,int>::iterator it=hash.find(target-nums[i]);
            if(it!=hash.end())
             {return{it->second,i};}
            hash[nums[i]]=i;
        }
        return{};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

其涉及的c++相关：

find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end()

size(); //返回容器中元素的数目

(*it).first会得到key，
(*it).second会得到value。
这等同于it->first和it->second。

在官方答案中
采用unordered_map

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 {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

map用法：

find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end(); count(key);
//统计key的元素个数

unordered_map和map的区别

unto关键字的使用