代码随想录训练营Day06 | 454.四数相加II - 383. 赎金信 - 15. 三数之和 - 18. 四数之和
454.四数相加II
- 题目链接：454.四数相加II
- 思路：本题思路主要是将 num1 + nums2 + num3 + num4 = 0 转化成 num1 + num2 = -num3 - num4上，转换之后就是枚举左边，然后选择右边，使用哈希表维护前一个的值，然后遍历等式右边的值，符合就统计次数；
- 代码：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> cnt;
int ans = 0, n = nums1.size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cnt[nums1[i] + nums2[j]]++; // 统计等式左边的和
}
}
for(int c : nums3){
for(int d : nums4){
int target = 0-(c+d); // 等式右边的值
auto iter = cnt.find(target); // 存在
if(iter != cnt.end()){
ans += iter->second; // 统计次数
}
}
}
return ans;
}
};
383. 赎金信
- 题目链接：383. 赎金信
- 思路：本题依然是一个次数统计的问题，分别统计ransomNote和magazine字符串中每个字符串的次数，根据题意可得，magazine字符串中每个字符出现次数必须大于等ransonNote中对应每个字符出现次数。
- 代码：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int n = ransomNote.size(), m = magazine.size();
vector<int> cntn(26, 0);
vector<int> cntm(26, 0);
for(int i = 0, j = 0; i < n || j < m; ++i, ++j) {
if(i < n)
cntn[ransomNote[i] - 'a']++;
if(j < m)
cntm[magazine[i] - 'a']++;
}
for(int i = 0; i < 26; i++) {
if(cntm[i] < cntn[i])
return false;
}
return true;
}
};
15. 三数之和
-
题目链接：15. 三数之和
-
思路：
- 本题思考方向和上面第一题类似，需要变换等式，num1 + num2 + num3 = 0 -> num1 = - num2 + num3，变换之后就是枚举左边，然后维护右边两个数，枚举和维护过程中根据题意需要跳过重复的值；
- 注意根据题意，本题只需要数组中的值，不考虑下标顺序，故为了方便可以将数组排序，排序之后，枚举左边这个数，维护右边两个数，右边两个数因为数组排序了，可以使用双指针，相向遍历。
- 详细题解附 卡哥讲解，灵神讲解
-
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
ranges::sort(nums);
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n - 2; i++) { // 枚举左边
int x = nums[i];
if (i && x == nums[i - 1]) continue; // 跳过重复数字
if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化一
if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二
int j = i + 1, k = n - 1; // 维护右边两个，双指针
while (j < k) {
int s = x + nums[j] + nums[k];
if (s > 0) {
k--;
} else if (s < 0) {
j++;
} else { // s == 0
ans.push_back({x, nums[j], nums[k]}); // 符合条件
for (j++; j < k && nums[j] == nums[j - 1]; j++); // 跳过重复数字
for (k--; k > j && nums[k] == nums[k + 1]; k--); // 跳过重复数字
}
}
}
return ans;
}
};
18. 四数之和
- 题目链接：18. 四数之和
- 思路：
- 本题思路和上面三数之和一致，这里要枚举两个数，然后另外两个数使用双指针；
- 排序后，枚举 nums[i] 作为第一个数，枚举 nums[f] 作为第二个数，那么问题变成找到另外两个数，使得这四个数的和等于 target，这可以用双指针解决；
- 本题详细讲解见卡哥讲解，灵神讲解
- 代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
ranges::sort(nums); // 排序
vector<vector<int>> ans;
for(int i = 0; i < n - 3; i++) { // 枚举第一个数
long long x = nums[i];
if(i > 0 && x == nums[i-1]) continue; // 跳过重复数字
if(x + nums[i+1] + nums[i+2] + nums[i+3] > target) break; // 优化
if(x + nums[n-1] + nums[n-2] + nums[n-3] < target) continue;
for(int j = i + 1; j < n - 2; j++) {
long long y = nums[j];
if(j > i + 1 && y == nums[j-1]) continue; // 同上
if(x + y + nums[j+1] + nums[j+2] > target) break;
if(x + y + nums[n-2] + nums[n-1] < target) continue;
int a = j + 1, b = n - 1; // 双指针
while(a < b) {
long long c = x + y + nums[a] + nums[b];
if(c > target) --b;
else if(c < target) ++a;
else {
ans.push_back({(int)x, (int)y, nums[a], nums[b]});
for(a++; a < b && nums[a] == nums[a - 1]; ++a);
for(b--; b > a && nums[b] == nums[b + 1]; --b);
}
}
}
}
return ans;
}
};