力扣454. 四数相加II
思路：把四个数组分为两组，前两组的和 + 后两组的和 = 0；
利用哈希表，key为前两组的和，value为出现的次数，因为根据题意，只需输出有几种情况，因此value设置为出现的次数，然后用后两组的和的负数，作为key查找，如果找到了就count += value。
最后返回count
代码
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> map1;
//unordered_map<int, int> map2;
int count = 0;
for (int i = 0; i < nums1.size(); i++)
{
for (int j = 0; j < nums2.size(); j++)
{
map1[nums1[i] + nums2[j]]++;
}
}
for (int i = 0; i < nums3.size(); i++)
{
for (int j = 0; j < nums4.size(); j++)
{
if (map1.find(-(nums3[i] + nums4[j])) != map1.end())
{
count += map1[-(nums3[i] + nums4[j])];
}
}
}
return count;
}
力扣383. 赎金信
思路：先统计magazine，每个字母++；然后遍历ransomNote，每个字母--；
如果哈希表里的数值小于0，那么说明这个字母缺少直接返回false，否则返回true。
注意：如果先遍历ransomNote，再遍历magazine，那么需要完全遍历结束后，再判断哈希表里是否有值小于0，所以应该先遍历ransomNote。
代码
bool canConstruct(string ransomNote, string magazine) {
int record[26] = {0};
for (int i = 0; i < magazine.size(); i++)
{
record[magazine[i] - 'a']++;
}
for (int i = 0; i < ransomNote.size(); i++)
{
record[ransomNote[i] - 'a']--;
if (record[ransomNote[i] - 'a'] < 0)
{
return false;
}
}
return true;
}
力扣15. 三数之和
挺难的，思路+去重
思路：先排序，为后面做准备。然后遍历nums，i作为固定的，然后左右双指针，如果大于0，则收缩右指针，如果小于0则收缩左指针。重点在于去重！
初始情况，第一次循环，遍历nums，设置双指针。
刚好等于0，记录结果{-2,0,2}；
然后左右收缩
此时也等于0，但是需要去重，去重的逻辑就是如果找到一个答案了，并且他左右指针的下一个正好和现在这个相等，就跳过下一个，为什么？因为i是固定的，如果left的下一个等于现在这个，那么right即使找到了，也必定是现在这个值，就必定重复，因此，直接跳过。这是左右指针的去重。
此外还有i的去重，如果i等于前一个，那么直接跳过。此记录为二刷，只做记录，不做发布。
代码如下：
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > 0)
{
break;
}
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right)
{
if (nums[i] + nums[left] + nums[right] == 0)
{
result.push_back({ nums[i], nums[left], nums[right] });
while (right > left && nums[right] == nums[right - 1])
{
right--;
}
while (right > left && nums[left] == nums[left + 1])
{
left--;
}
right--;
left++;
}
else if (nums[i] + nums[left] + nums[right] > 0)
{
right--;
}
else
{
left++;
}
}
}
return result;
}
力扣18. 四数之和
此题与三数之和无异，掌握此题，可以做7数之和，8数之和，随便。
三数之和，就是固定一个i，然后双指针，将On3复杂度降为On2，四数之和，便是固定两个数i，j，将On4复杂度降为On3，多套一层循环罢了。重点在剪枝，去重！每层循环都要剪枝。
代码：
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//此题与三数之和的区别在于，这题有时候会给数组里根本没有4个数。直接返回
if (nums.size() < 4)
{
return {};
}
vector<vector<int>> result;
sort(nums.begin(), nums.end());
//第一层循环，固定i。
for (int i = 0; i < nums.size(); i++)
{
//对i剪枝，因为上题target是0，这题不是，所以不能随便剪。如果前面是正数，并且第一个数大于target了，剪枝，why?
//因为如果数组是【-4，-3，-2，-1】，target = -10；那么是可以凑出来的，但是nums[i] > target.
//其实可以从尾部继续剪枝，最后一个数如果小于0，并且最后一个数小于target，那么剪枝，试了一下，时间提升不大，可能示例没那么多。
if (nums[i] > target && nums[i] >= 0)
{
break;
}
//去重操作，如果i>0（保证不会出现i-1 < 0数组越界），并且重复，直接跳过
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
//第二层循环，固定j
for (int j = i + 1; j < nums.size(); j++)
{
//如果两个固定的数大于target，并且大于0， 剪枝
if (nums[j] + nums[i] > target && nums[j] + nums[i] >= 0)
{
break;
}
//去重。
if (j > i + 1 && nums[j] == nums[j - 1])
{
continue;
}
int left = j + 1;
int right = nums.size() - 1;
while (left < right)
{
if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target)
{
right--;
}
else if ((long)nums[i] + nums[j] + nums[left] + nums[right] < target)
{
left++;
}
else
{
result.push_back({nums[i], nums[j], nums[left], nums[right]});
//去重后两个数。
while (left < right && nums[left] == nums[left + 1])
{
left++;
}
while (left < right && nums[right] == nums[right - 1])
{
right--;
}
left++;
right--;
}
}
}
}
return result;
}