行业知识
力扣 | 哈希表2 | 454.四数相加||，383.赎金信，15.三数之和，18.四数之和
���录
454.四数相加||
383.赎金信
15.三数之和
18.四数之和
总结
454.四数相加||
解决办法：
总体思路是先遍历前两个数组得到a+b以及相加后的结果的次数，再遍历后两个数组得到c+d，然后在前面两个数组所得到的集合中去找是否有0-(c+d)的值，
- 为何用哈希表：这里需要查找是否出现过
- 为何用map：哈希值由题可能会很大，不仅要找到该元素，还要找到其所出现的次数。故key来保存数值，value保存次数。即key,value并不总是一个保存元素一个保存下标的关系，具体对应什么，根据题目而定。
- 本题不需要去重，四个数组，可以有重复的四个元素相加等于一的情况，即需要统计次数。不同位置的元组，次数都会加一。
语法：map[a+b]++可以实现对应元素的value相应+1操作，以及insert(a+b)
class Solution {public: int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) { unordered_map map; // 前两个数组 for (int a : nums1) { for (int b : nums2) { map[a + b]++; // 统计数值和出现次数 } } // 后两个数组 int count = 0; for (int c : nums3) { for (int d : nums4) { int target = 0 - (c + d); // 需找的元素 if (map.find(target) != map.end()) { count += map[target]; // 加value而不是单纯+1 } } } return count; }};时间复杂度O(n^2)
空间复杂度O(n^2)
383.赎金信
解决办法：和有效的字母异位词相似。题目说了也是只有小写字母，故可以用长度26的数组。注意长度有效性的判断。
该题也可以暴力法两个for循环（ransomNote.erase(ransnomNote.begin()+j，在ransomNote找到该字符了就删除，最终ransomNote.length()==0为空，则true），只不过不用额外开辟数组空间，但时间低下了。
length()用于字符串的字符数量，size()用于容器vector的大小。字符串能用索引[]
class Solution {public: bool canConstruct(string ransomNote, string magazine) { int nums[26] = {0}; // 后者长度不够，直接pass if (magazine.length() 0) { nums[ransomNote[i] - 'a']--; } else { return false; } } return true; }};时间复杂度O(n)
空间复杂度O(1)
15.三数之和
解决办法：本题注意，需要去重，三元组内的元素不可和另一个三元组重复即使元素来自不同下标。
双指针法（要排序），将时间复杂度O(n^2)的解法优化为O(n)的解法，即降一个数量级
将数组由低到高进行排序后，for循环，i从数组第一个位置开始，left从第二个位置开始，right从最后一个位置开始，三个数相加大于零，则right--，三数相加小于零，则left++,等于零，则找到一组。这个过程里，i,left,right都要进行去重，比如nums[i]==nums[i-1]则说明这个元素及其所对应的那一组已经出现过了，就要进行i++的操作，继续去找下一组才行。（注意这里不是判断nums[i]==nums[i+1]，这种是判断的三元组内的三个元素是否重复了，这种由题意是可以的）。有点像滑动窗口，left和right间的区域也是在不断缩小以找到所需元素。
注意去重的写法以及去重和获取结果间的先后关系。left和right的去重，注意是使用while而不是if，因为可能连着几个数都是一样的。找到结果后，双指针得同时收缩。i是与前一个比，前面有了，就直接下一个；left,right和下一个比，已经收集了，就不收集了。i定了，后面的left和right也是定了。
sort(nums.begin(), nums.end());
vector result;
result.push_back(vector{nums[i], nums[left], nums[right]});
class Solution {public: vector threeSum(vector& nums) { vector result; sort(nums.begin(), nums.end()); for (int i = 0; i 0) { return result; } // 前提i>0,才可i-1。i去重 if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1; int right = nums.size() - 1; // right==left时，后面两个元素都合二为一变成同一个元素了，哪来三元组 while (right > left) { if (nums[i] + nums[left] + nums[right] > 0) { // 大了就缩小 right--; } else if (nums[i] + nums[left] + nums[right] left，外层的right>left是外层的，这里在去重时，可能就不满足这个前提了，所以需要加入If条件里 // 注意这里是left和left+1,right和right-1！！！！！！已经收割到一组了，故接下来重复的直接跳过，不同于i while (right > left && nums[left] == nums[left + 1]) { left++; } while (right > left && nums[right] == nums[right - 1]) { right--; } // 找到时，双指针需同时收缩 left++; right--; } } } return result; }};时间复杂度O(n^2)for和while
空间复杂度O(1)题目本身给的就是二维空间了
18.四数之和
解决办法：
类似三数之和，也用双指针，不过这里有两个for循环，两重剪枝和去重。
注意两个负数相加可能更小。这里是target不是三数之和那样的0，该target可能为负数，故不能简单剪枝nums[k]>target，还需要前提nums[k]>=0 || target>=0.
三数之和的解法是一层for循环nums[i]为确定值，循环内有left和right双指针；四数之和的解法是两层for循环nums[k]+nums[i]为确定值，依然循环内是left和right双指针。
四数相加可能极大，为避免溢出，故需转为long类型
class Solution {public: vector fourSum(vector& nums, int target) { vector result; sort(nums.begin(), nums.end()); for (int k = 0; k target && target >= 0) break; // 使用break,统一通过最后的return返回 // 一重去重 if (k > 0 && nums[k] == nums[k - 1]) continue; for (int i = k + 1; i target && nums[i] + nums[k] >= 0) break; // 二重去重 if (i > k + 1 && nums[i] == nums[i - 1]) continue; // 类似三数之和的逻辑，只不过这里变成了四元 int left = i + 1; int right = nums.size() - 1; while (right > left) { if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) right--; else if ((long) nums[k] + nums[i] + nums[left] + nums[right] left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; // 双指针收缩 left++; right--; } } } } return result; }};时间复杂度O(n ^ 3)
空间复杂度O(1)
总结
下一篇：怎么禁掉服务器?
