LeetCode?454. 四数相加 II
思路：
和1. 两数之和的思路也是一样的，代码结构也差不多，区别只是把nums1和nums2的元素相加的所有结果放在一个hashmap，并记录下结果出现的次数，然后用target（本题中为0）减去nums3和nums4的元素相加的所有结果求得差值，并在hashmap中寻找是否有这两者的差值，如果有的话就把对应的差值的次数加到count。
代码：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> hashmap;
for (int i = 0; i < nums1.size(); i++)
{
for (int j = 0; j < nums2.size(); j++)
{
hashmap[nums1[i]+nums2[j]]++;
}
}
int count = 0;
for (int i = 0; i < nums3.size(); i++)
{
for (int j = 0; j < nums4.size(); j++)
{
auto a = hashmap.find(0-(nums3[i]+nums4[j]));
if (a != hashmap.end())
count += a->second;
}
}
return count;
}
};时间复杂度：O(m^2+n^2)
空间复杂度：O(m+n)
LeetCode 383. 赎金信?
思路:
和242. 有效的字母异位词思路完全一样，甚至可以用相同的代码，本质就是用hashset选出相同的元素，如不相同（字符出现频率为负）则返回false。
代码：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if (ransomNote.size() > magazine.size())
return false;
vector<int> count(26);
for (int i = 0; i < magazine.size(); i++)
count[magazine[i] - 'a']++;
for (int i = 0; i < ransomNote.size(); i++)
{
if (--count[ransomNote[i] - 'a'] < 0)
return false;
}
return true;
}
};时间复杂度：O(n)
空间复杂度：O(1)
LeetCode?15. 三数之和
思路：
乍一看和1. 两数之和非常的相似，但其实做法完全不同，因为如果按照哈希表的做法，去重会是一个非常麻烦的问题，因为题目要求的是返回值而不是返回索引，就会出现索引不同但值相同的情况，哈希表没有办法避免这种情况，去重的逻辑非常难写，所以这里采用三指针的做法。
三指针分别表示a，b，c的索引，然后我们需要求得a+b+c=0时的所有可能的值。首先要对数组排序，取一个指针i，从0开始遍历数组，然后再取另外两个指针left和right，分别指向i的下一位和数组的末尾，然后求nums[i]+nums[left]+nums[right]的和。因为数组是排过序的，当和小于0时，left指针向右移，当和大于0时right指针向左移，当和等于0时，同时收缩left和right，当left和right相遇的时候，i指针向右移一格，然后重新给left和right赋值，执行上述操作，直到i指向数组的末尾倒数第三个元素。为什么是倒数第三个而不是最后一个？因为要给left和righ指针留位置，我们知道三个指针指向的位置不能重复，这种情况下left和right分别指向倒数第二个和最后一个元素。
接下来要考虑去重的问题，left和right指针去重是在当和等于0的时候，先通过两个循环把left和right移动到最后一个相同的元素，然后再收缩指针，这么做是为了保障在下个循环内left和right指向的都是不同的元素。i的去重是考虑i和i-1的情况，也就是说在i当前指向的元素和i上一个指向的元素有重复的时候才跳过，但为什么不是和下一个元素比较呢？因为实际上数组内是可以有重复元素的，如{-1，-1，2}就是一个解，这么做会直接跳过这个解。
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int size = nums.size();
for (int i = 0; i < size - 2; i++)
{
// 排序后如果第一个元素大于0，直接返回
if (nums[i] > 0)
return ans;
// 给i去重，必须和i-1比较
if (i > 0 && nums[i] == nums[i-1])
continue;
int right = nums.size() - 1;
for (int left = i + 1; left < right;)
{
if (nums[i]+nums[left]+nums[right] == 0)
{
ans.push_back({nums[i], nums[left], nums[right]});
// 先去重
while (left < right && nums[left] == nums[left + 1])
left++;
while (left < right && nums[right] == nums[right - 1])
right--;
// 找到答案时，双指针同时收缩
left++;
right--;
}
else if (nums[i]+nums[left]+nums[right] < 0)
left++;
else
right--;
}
}
return ans;
}
};时间复杂度：O(nlogn+n^2)
空间复杂度：O(1)~O(n!)
LeetCode?18. 四数之和
这题选用和15. 三数之和一样的方法做，同样也是先排序再用几个指针的方法。a、b、c、d四个指针分别指向四个数，c和d的去重方法和15. 三数之和中b和c的去重方法是一样的，在最外层循环的a的去重方法也是一样的，唯一要注意的是b的去重，b的去重条件虽然也是和前一个数也就是b-1进行比较，但是要注意b还要同时大于a+1而不是大于0或大于1，原因是要确保和b重复的数b-1不能和a是一个数，也就是ab-1。
其他要注意的点则是，考虑到数组中有可能会出现很大的数，int可能会overflow，可以在加法中显示转换成long。还有剪枝的条件也需要注意，因为数组是排序过的，a的剪枝条件为nums[a]>target并且nums[a]>0，b的剪枝条件为nums[a]+nums[b]>target而不能只是nums[b]，同时两者的和也需要大于0。
代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int a, b, c, d;
vector<vector<int>> ans;
if (nums.size() < 4)
return ans;
sort(nums.begin(), nums.end());
for (a = 0; a < nums.size() - 3; a++)
{
// 剪枝
if (nums[a] > target && nums[a] >= 0)
break;
if (a > 0 && nums[a] == nums[a - 1])
continue;
for (b = a + 1; b < nums.size() - 2; b++)
{
// 剪枝
if (nums[a] + nums[b] > target && nums[a] + nums[b] >= 0)
break;
if (nums[b] == nums[b - 1] && b > a + 1)
continue;
d = nums.size() - 1;
for (c = b + 1; c < d;)
{
if ((long)nums[a]+nums[b]+nums[c]+nums[d] == target)
{
ans.push_back({nums[a], nums[b], nums[c], nums[d]});
// 去重
while (c < d && nums[c] == nums[c + 1]) c++;
while (c < d && nums[d] == nums[d - 1]) d--;
//收缩
c++;
d--;
}
else if ((long)nums[a]+nums[b]+nums[c]+nums[d] < target)
c++;
else
d--;
}
}
}
return ans;
}
};时间复杂度：O(nlogn+n^3)
空间复杂度：O(1)~O(n!)