1. 两数之和

1. 两数之和 - 力扣（LeetCode）

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路

本题不能用滑动窗口来做！滑动窗口只适用于找连续的元素！！！！比如说，找数组中长度最小的子数组。

本题有两种解法，一种是用map，一种是用set。个人理解的，set的做法和map的差不多。如果用map来做，需要了解：

pair是结构体，用于将两个不同类型的数据组合在一起，常用于STL中的map或函数值返回。

访问pair中的元素分别为 first、second。

​ 用法：pair<type,type>(n,n)

auto： 自动获取变量的类型。例如 auto n = （int） a。此时n的数据类型就是int

unordered_map.insert(key,value);

map容器第一个存的是key值，就是下标值，第二个是value，就是存储的值。

unordered_map底层实现也是hash表

第一种，用unordered_set实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_set<int> hash(nums.begin(),nums.end());//先把值全部存入set中
        int j,i;
        vector<int> ans ;
        for(i = 0;i<nums.size();i++){
            int temp = target - nums[i];
            if(hash.find(temp) != hash.end()){//如果发现set中有要找的值
                for(j = i+1 ; j<nums.size();j++){//从当前位置的下一位开始遍历
                    if(nums[j] == temp){
                        ans = {i,j};
                        return ans;
                    }
                }
            }
        }
        return ans;
    }
};

第二种做法，用map：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(int n = 0; n <nums.size();n++){
            auto temp = map.find(target - nums[n]);
            if(temp != map.end()){
                return {temp->second ,n};
            }
            else{
                map.insert(pair<int,int>(nums[n],n));//注意pair的使用
            }
        }
        return {};
        
    }
};