【算法训练营day7】LeetCode454. 四数相加II LeetCode383. 赎金信 LeetCode15. 三数之和 LeetCode18. 四数之和
LeetCode454. 四数相加II
题目链接：454. 四数相加II
初次尝试
没有思路，对于map的使用还不是非常熟练，正好借这几个题多练习一下。
看完代码随想录后的想法
四个数组两两一组，写成两个嵌套的for循环，这样可以保证时间复杂度最小，其中使用map的原因是不仅要统计前两个数组的元素和，还要统计每个和出现的次数。
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> hashMap;
int count = 0;
for (int i = 0; i < nums1.size(); i++) {
for (int j = 0; j < nums2.size(); j++) {
auto iter = hashMap.find(nums1[i] + nums2[j]);
if (iter != hashMap.end()) {
iter -> second++;
}
else {
hashMap.insert(pair<int, int>(nums1[i] + nums2[j], 1));
}
}
}
for (int i = 0; i < nums3.size(); i++) {
for (int j = 0; j < nums4.size(); j++) {
auto iter = hashMap.find(0 - nums3[i] - nums4[j]);
if (iter != hashMap.end()) {
count += iter -> second;
}
}
}
return count;
}
};
LeetCode383. 赎金信
题目链接：383. 赎金信
初次尝试
感觉和242. 有效的字母异位词是一个思路的题，解起来不难，一遍ac。
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> hashVec(26, 0);
for (int i = 0; i < magazine.size(); i++) {
hashVec[magazine[i] - 'a']++;
}
for (int i = 0; i < ransomNote.size(); i++) {
hashVec[ransomNote[i] - 'a']--;
if (hashVec[ransomNote[i] - 'a'] < 0) {
return false;
}
}
return true;
}
};
看完代码随想录后的想法
思路一样。
LeetCode15. 三数之和
题目链接：15. 三数之和
初次尝试
思路比较混乱，没有想到解法。
看完代码随想录后的想法
这题应该是刷题刷到现在，思考量最大的一道题了，很容易想着想着陷入疑惑，最好边画图边想。这里按照思考顺序列举几个解题的关键点：
为什么上来要先排序？LeetCode官方题解中对此有非常清楚的解释。
「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：
第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
也就是说，我们枚举的三元组 (a, b, c) 满足a≤b≤c，保证了只有 (a, b, c)这个顺序会被枚举到，而 (b, a, c)、(c, b, a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。
但是仅仅排序之后就可以保证输出的三元组不重复了吗？不一定，排序过后的数组仍然可能存在连续相等的元素，这可能会导致在遍历过程中，连续几个循环a取得相同的值，导致输出重复的三元组，b和c同理，所以仍然需要对abc去重。
但是对于a和bc的去重方式又有所差别，对于b和c，我们可以在left和right指针指向的下一个元素和现在指向的元素相等的时候，直接跳过下一个元素；而对于a，我们需要考虑特殊的情况，比如遇到{0, 0, 0}或者{-1, -1, 2}这样的输入时，如果使用nums[i] == nums[i + 1]这样的判断，就会漏掉(0, 0, 0)或者(-1, -1, 2)这样的三元组，所以对于a，应该使用nums[i] == nums[i - 1]这样的判断，这样才能保证既不漏掉特殊情况，又不输出因为a重复而重复的三元组。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) {
return ans;
}
// 对a去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = nums.size() - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] < 0) {
left++;
}
else if (nums[i] + nums[left] + nums[right] > 0) {
right--;
}
else {
ans.push_back(vector<int>{nums[i], nums[left], nums[right]});
// 对b和c去重
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return ans;
}
};
LeetCode18. 四数之和
题目链接：18. 四数之和
初次尝试
算是三数之和的拓展题，本质上就是在三数之和的基础上再加一层for循环，但是在实际写的过程中有几个细节需要注意。
看完代码随想录后的想法
两点细节需要注意：
- 剪枝处理的判断条件和三数之和不同，内外两层剪枝处理的返回语句不同。
需要在四数求和的时候将int强制转型为long int，防止溢出。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
// 剪枝处理
if (nums[i] > target && nums[i] >= 0) {
return ans;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.size(); j++) {
// 2级剪枝处理
if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) {
break;
}
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1, right = nums.size() - 1;
while (left < right) {
// 强制转型
if ((long) nums[i] + nums[j] + nums[left] + nums[right] < target) {
left++;
}
else if ((long) nums[i] + nums[j] + nums[left] + nums[right] > target) {
right--;
}
else {
ans.push_back(vector<int>{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 ans;
}
};
