随想录Day7|454. 四数相加Ⅱ、383. 赎金信、15. 三数之和、18. 四数之和
454. 四数相加Ⅱ
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
提示：
1 <= n <= 200-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
第一想法
如果用map存“值：下标”，可是总共有四个数，不能和昨天一样target - num这样找到两个数中的另一个了。如果暴力三重循环而用0减去前三个数得到最后一个数的值，时间复杂度就有\(O(n^3)\)，显然也不对。而且要下标有什么用呢？显然也不太合理。昨天那道“两数之和”是要求下标的，但是这里只要求计数。
四个数组长度都一样且不超过200。长度一样，一定是一个会用到的性质……
看了随想录题解的想法
化归的思想，最终简化成类似两数之和！把四个数组分两组处理，遍历用map的key记录a+b的值和出现的次数，然后遍历后两个数组，看看0 - (c + d)是否在map中出现过，如果是，则对应的次数叠加到count中。之前两数之和是要下标，所以map的second记录下标，这里要次数，所以记录次数，非常合理。而且记录次数的思想又在“有效字母的异位词”中用到过。
复杂度分析
时间复杂度：\(O(n^2)\)，因为两层循环是\(O(n^2)\)。
空间复杂度：\(O(n^2)\)，因为最坏情况下每个a + b都不相同，需要记录\(n^2\)个key。
用时24min~
int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4)
{
int count = 0;
unordered_map<int, int> map;
for (int a : nums1)
{
for (int b : nums2)
map[a + b]++;
}
for (int c : nums3)
{
for (int d : nums4)
{
if (map.find(-c - d) != map.end())
count += map[-c - d];
}
}
return count;
}
383. 赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
1 <= ransomNote.length, magazine.length <= 105ransomNote和magazine由小写英文字母组成
第一想法
先扫描magazine，只有小写英文字母所以用数组即可，先记录每个字母出现次数，然后扫描ransomNote时次数自减（用掉一个），最后如果数组每个数都非负就是true，一旦出现负数就返回false。
复杂度分析
时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)
用时6min~
bool canConstruct(string ransomNote, string magazine)
{
int freq[26] = {0};
for (int i = 0; i < magazine.length(); i++)
freq[magazine[i] - 'a']++;
for (int i = 0; i < ransomNote.length(); i++)
freq[ransomNote[i] - 'a']--;
for (int i = 0; i < 26; i++)
{
if (freq[i] < 0)
return false;
}
return true;
}
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
3 <= nums.length <= 3000-105 <= nums[i] <= 105
第一想法
和四数相加不一样，这里需要考虑去重的因素。而且这里要的是元组本身，需要返回的每个三元组加起来都是0。则直接用之前一样存和的方法就会丢失信息。而且卡尔在提示里面也说哈希法会很麻烦，正解是双指针法。
也就是这两个指针以\(O(n^2)\)的方式遍历，每次找是否有一个不一样的值使得三数之和为0？找一个元素是否存在，应该联想到哈希，但是如果找到重复的？因为find有结果，那个结果也可能就是指针已经指着的两个数之一。
看了随想录题解后的想法
首先将数组排序，然后有一层for循环，
i从下标0的地方开始，同时定一个下标left 定义在i + 1的位置上，定义下标right 在数组结尾的位置上。依然还是在数组中找到
a b c使得a + b + c =0，我们这里相当于a = nums[i]，b = nums[left]，c = nums[right]。接下来如何移动left 和right呢， 如果
nums[i] + nums[left] + nums[right] > 0就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。如果
nums[i] + nums[left] + nums[right] < 0说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
已经说得很清楚了！而且其实这么说应该是三指针了。
之所以要跳过和上一轮同样的left和right，是因为只有三个数，因此在内层循环中，这两个数只要有一个和上一轮一样，另一个也一定和上一轮一样，则造成了重复的三元组。
遇到的问题
这是第一次用LeetCode插件debug，主要还是在去重这一步，这三个数中但凡遇到了和上一轮循环一样的数字，都要一直向后/向前跳过，直到达到新的值。其中l和r的移动应该让r先左移，因为一定有一个l > 0给它兜底，但是如果l往右，可能会超出范围。
以输入[0,0,0,0]为例，如果l = 1，r = 3，则l的右移会一路移到3，r不动，然后在l++这一步直接超出数组范围。所以需要先移动r，以此约束l。
复杂度分析
时间复杂度：\(O(n^2)\)
空间复杂度：\(O(1)\)
用时40min~
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> result;
sort(nums.begin(), nums.end());
int len = nums.size();
// 先排除特殊情况，即全正或全负
if (nums[0] > 0 || nums[len - 1] < 0)
return result;
for (int i = 0; i < len - 2; i++)
{
// 我们要在nums[i]右边找两个数，如果已经>0，则不可能三数和为0
if (nums[i] > 0)
return result;
// 对nums[i]也要注意不要和上一轮走到同一个值
if (i > 0 && nums[i] == nums[i - 1])
continue;
int l = i + 1;
int r = len - 1;
int sum = nums[i] + nums[l] + nums[r];
while (l < r)
{
if (sum == 0)
{
result.push_back(vector<int>{nums[i], nums[l], nums[r]});
// 让left和right同时向内，走到与刚刚不同的值
while (l < r && nums[r] == nums[r - 1])
r--; // 此处必须r先走，否则l可能走到超出上限
while (l < r && nums[l] == nums[l + 1])
l++;
l++;
r--; // 此时它们都抵达了下一个不一样的值的下标
}
else if (sum > 0)
r--;
else
l++;
sum = nums[i] + nums[l] + nums[r];
}
}
return result;
}
18. 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
提示：
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
第一想法
比起四数相加，这里多了去重，也许这里需要四个指针？先排序，再遍历，里层的循环只看外层指针右侧的元素即可，就是比三数之和多了一层循环。
遇到的问题
wrong answer，大部分都过了，不过对于这个样例：
[-2,-1,-1,1,1,2,2]
0
Answer Expected Answer
[[-2,-1,1,2]] [[-2,-1,1,2],[-1,-1,1,1]]
我没有统计上后一个，但是在我完善了剪枝判断之后，这个错误就解决了。在第二层循环关于j的判断中，我错误地写成了j > 1，但是应该是j > i + 1。因为是允许第二个数字和第一个数字值重复的，所以第二个数字的去重只在自己可以变换的范围比较，即第一个数字的右侧。
还有就是四个数相加可能溢出int的范围，因此改用long long。
复杂度分析
时间复杂度：\(O(n^3)\)
空间复杂度：\(O(1)\)
用时37min~
vector<vector<int>> fourSum(vector<int> &nums, int target)
{
vector<vector<int>> result;
sort(nums.begin(), nums.end());
int len = nums.size();
for (int i = 0; i < len - 3; i++)
{
if (nums[i] >= 0 && nums[i] > target)
break;
if (i > 0 && nums[i] == nums[i - 1])
continue;
for (int j = i + 1; j < len - 2; j++)
{
long long sum_ij = nums[i] + nums[j];
if (sum_ij >= 0 && sum_ij > target)
break;
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
int l = j + 1;
int r = len - 1;
long long sum_all = sum_ij + nums[l] + nums[r];
while (l < r)
{
if (sum_all == target)
{
result.push_back(vector<int>{nums[i], nums[j], nums[l], nums[r]});
while (l < r && nums[r] == nums[r - 1])
r--;
while (l < r && nums[l] == nums[l + 1])
l++;
l++;
r--;
}
else if (sum_all < target)
l++;
else
r--;
sum_all = sum_ij + nums[l] + nums[r];
}
}
}
return result;
}
碎碎念
今天也是上午写完，难熬的数据库有了完美的度过方法，真好。今天学到了哈希法和双指针法，真的很巧妙。