两数之和

leetcode.1

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

这个题暴力解也能过，但这里可以用hashmap降复杂度。

需要注意的是一个元素不能用两遍，所以要做特判！！

#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int, int> numIn;
        for (int i = 0; i<nums.size();i++) {
            numIn.emplace(nums[i],i);
        }
        for (int i = 0; i<nums.size(); i++) {
            if ( numIn.find(target-nums[i])!=numIn.end()&&numIn[target-nums[i]]!=i) {
                res.emplace_back(i);
                res.emplace_back(numIn[target-nums[i]]);
                return res;
            }
        }
        return res;
    }
};

类题：四数相加

leetcode.454

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

两个数变四个数，同样用哈希的道理，拆成两两一组。

为什么两两一组？

同样是a+b+c+d=0，可以化为a+b=-(c+d)，也可以化为a=-(b+c+d)，甚至可以追问，为什么要拆开。

原因是最低复杂度，求和两个数组和的结果出现次数复杂度为O2，三个就是O3，四个就是O4。所以可以拆成两组，每组两个数，就是2*O2的复杂度，是最优的。

拆完之后，直接把和打个哈希表，遍历一个查询另一个就可以了。

#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> AandB;
        for (int i : nums1) {
            for (int ii : nums2) {
                AandB[i+ii]++;
            }
        }
        unordered_map<int, int> CandD;
        for (int i : nums3) {
            for (int ii : nums4) {
                CandD[i+ii]++;
            }
        }
        int res = 0;
        for (auto pair : AandB) {
            if (CandD[0-pair.first]!=0) {
                res+= pair.second*CandD[0-pair.first];
            }
        }
        return res;
    }
};

变题：三数之和 四数之和

leetcode.15 leetcode.18

好难，先放着