二刷代码随想录算法训练营第七天 |454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

题目链接：力扣

文章讲解：代码随想录

视频讲解： 学透哈希表，map使用有技巧！LeetCode：454.四数相加II

题目：

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

代码：

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> map;int ans=0;/*for(int i=0;i<nums1.size();i++)//两组合一{for(int j=0;j<nums1.size();j++){map[nums1[i]+nums2[j]]++;}}for(int i=0;i<nums1.size();i++)//两组合一{for(int j=0;j<nums1.size();j++){// if(map.find(-(nums3[i]+nums4[j])) != map.end())//hash查询增加时间ans += map[-(nums3[i]+nums4[j])];//默认构造0}}*/for(int &i:nums1)//指针速度更快for(int &j:nums2)map[i + j]++;for(int &i:nums3)for(int &j:nums4)//if(map.find(-(i+j)) != map.end())//hash查询增加时间ans += map[-(i+j)];//默认构造0return ans;}
};

//用哈希数组替代map减去哈希计算的时间。
class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());sort(nums3.begin(), nums3.end());sort(nums4.begin(), nums4.end());int n = nums1.size();int low = min(nums1[0]+nums2[0], -nums3[n-1]+-nums4[n-1]);int high = max(nums1[n-1]+nums2[n-1], -nums3[0]+-nums4[0]);int range = high - low + 1;vector<int> hash(range, 0);int ans = 0;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)hash[nums1[i]+nums2[j] - low]++;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++){int find = -nums3[i]+-nums4[j]-low;if (hash[find] != 0)ans += hash[find];}return ans;}
};

时间复杂度: O(n^2)                                        空间复杂度: O(n^2)

⏲：8:52

总结：1.将map当数组用，其下标相当于key，数组的值则为value。2.若访问map中不存在的值，就会构造一对key和value，且value为0。3.循环用指针的速度大于变量。4.形如x1+x2+....=k可变成x1=k-x2-x3... 方便查找。

题目链接：力扣

文章讲解：代码随想录

视频讲解：

题目：给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。

代码：

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int hash[26] = {0};for(auto i : ransomNote)hash[i-'a']++;for(auto i : magazine)hash[i-'a']--;for(int i = 0; i < 26; i++)if (hash[i] > 0)      return false;return true;}
};

时间复杂度: O(n)                                        空间复杂度: O(1)

⏲：2:26

三、15. 三数之和18. 四数之和

15题目链接：力扣

18题目链接：力扣

文章讲解：代码随想录

视频讲解：梦破碎的地方！| LeetCode：15.三数之和

题目：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

代码：

三数之和：

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 < nums.size(); i++){if (nums[i]>0) break;if (i>0 && nums[i] == nums[i-1]) continue;unordered_set<int> set;for (int j = i+1; j < nums.size(); j++) {if (j > i+2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2]) continue;int t = -(nums[i] + nums[j]);if (set.find(t) != set.end()) {ans.push_back({nums[i], nums[j], t});set.erase(t);} else set.insert(nums[j]);}}return ans;*/
//双指针sort(nums.begin(), nums.end());vector<vector<int>> ans;int size = nums.size();for(int i = 0; i < size-2; i++){if (i>0 && nums[i] == nums[i-1]) continue;for(int left = i+1, right = size-1; left<right;){int sum = nums[i] + nums[left] + nums[right];if (sum>0) right--;else if(sum<0) left++;else{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--;right--;left++;}}}return ans;}
};

四数之和：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ans;if (nums.size() < 4) return ans;sort(nums.begin(), nums.end());for (int k = 0; k < nums.size() - 3; k++) {if (k > 0 && nums[k] == nums[k-1]) continue; if ((long)nums[k] + nums[k+1] + nums[k+2] + nums[k+3] > target) break; if ((long)nums[k] + nums[nums.size()-3] + nums[nums.size()-2] + nums[nums.size()-1] < target) continue; for (int i = k+1; i < nums.size()-2; i++) {if (i > k+1 && nums[i] == nums[i-1]) continue; int left = i+1, right = nums.size()-1;while (right > left) {long sum = (long)nums[k] + nums[i] + nums[left] + nums[right];if (sum > target) right--;else if (sum < target) left++;else {ans.push_back({nums[k], 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++;}}}}return ans;}
};

总结：1.剪枝：根据第一个数考虑后续相应数不可能成立的情况。2.去重：与前一个数比较是否相同，可以保障已经走过一遍，且第一个数的重复数的后续数的所有情况被包含于第一个数的前数中。中间原理相同。最后双指针部分，在保障已经有一次的情况下走完以避免直接退出循环。3.时间复杂度双指针降低一阶。双向指针可以快速跳过左右重复或差值过大的数。

哈希与双指针的适用：

1. 哈希法：不要求去重(去重繁琐) 或 要求返回元素下标（双指针需要排序）
2. 双指针法：要求去重 且 不要求返回元素下标