【算法训练营day7】LeetCode454. 四数相加II LeetCode383. 赎金信 LeetCode15. 三数之和 LeetCode18. 四数之和 _生活百科

【算法训练营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. 四数之和
初次尝试【【算法训练营day7】LeetCode454. 四数相加II LeetCode383. 赎金信 LeetCode15. 三数之和 LeetCode18. 四数之和】算是三数之和的拓展题，本质上就是在三数之和的基础上再加一层for循环，但是在实际写的过程中有几个细节需要注意。