代码随想录算法训练营第七天 | 454-四数相加II、383-赎金信、15-三数之和、18-四数之和
LeetCode454 四数相加II
题目链接：https://leetcode.cn/problems/4sum-ii/description/
文章讲解：https://programmercarl.com/0454.四数相加II.html
视频讲解：https://www.bilibili.com/video/BV1Md4y1Q7Yh/?vd_source=b989f2b109eb3b17e8178154a7de7a51
题目要求解有多少个元组(i，j，k，l)能满足nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0，不用去重，既可以分成两组
首先先用两层for循环遍历 nums1 和 nums2 数组，统计所有 nums1[i] + nums2[j] 和对应次数，用HashMap存储，Key为 nums1[i] + nums2[j] ，Value为出现的次数
要想找到符合 nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0 的情况次数，即在两层for循环遍历 nums3 和 nums4 数组时，累加所有HashMap中出现 0 - nums3[k] - nums4[l] 的情况对应的次数，即为最终答案
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {HashMap<Integer,Integer> ab = new HashMap<Integer,Integer>();for(int i = 0;i < nums1.length;i++){for(int j = 0;j < nums2.length;j++){int sum = nums1[i] + nums2[j];if(ab.containsKey(sum)){int cnt = ab.get(sum) + 1;ab.replace(sum, cnt);}else{ab.put(sum, 1);}}}int result = 0;for(int i = 0;i < nums3.length;i++){for(int j = 0;j < nums4.length;j++){int target = 0 - (nums3[i] + nums4[j]);if(ab.containsKey(target)){result += ab.get(target);}}}return result;}
}
LeetCode383 赎金信
题目链接：https://leetcode.cn/problems/ransom-note/description/
文章讲解：https://programmercarl.com/0383.赎金信.html
一拿到题目，首先想到的思路是先用HashMap，一层for循环遍历magazine字符串，统计magazine中出现的所有字符和对应次数
然后再一层for循环遍历ransomNote字符串，每个字符去HashMap中查找是否存在，若存在则次数减一，减到零则移除映射关系；若不存在，则返回false；全部遍历完则返回true
但是这个执行用时有点感人...因为用的是HashMap
题目提示中说了 ransomNote 和 magazine 由小写英文字母组成，其实能用一维数组代替HashMap，这样在数据量大的时候处理效率会更优，用时更少
class Solution {public boolean canConstruct(String ransomNote, String magazine) {HashMap<Character, Integer> dict = new HashMap<Character, Integer>();for(int i = 0;i < magazine.length();i++){char ch = magazine.charAt(i);if(dict.containsKey(ch)){int cnt = dict.get(ch);dict.replace(ch, cnt+1);}else{dict.put(ch, 1);}}for(int i = 0;i < ransomNote.length();i++){char target = ransomNote.charAt(i);if(dict.containsKey(target)){int cnt = dict.get(target);if(cnt == 1){dict.remove(target);}else{dict.replace(target, cnt-1);}}else{return false;}}return true;}
}
LeetCode15 三数之和
题目链接：https://leetcode.cn/problems/3sum/description/
文章讲解：https://programmercarl.com/0015.三数之和.html
视频讲解：https://www.bilibili.com/video/BV1GW4y127qo/?vd_source=b989f2b109eb3b17e8178154a7de7a51
梦破碎的地方hhh，一开始挺有思路，然后用哈希法越写越发觉不对劲，然后就一团浆糊，不知所措了...题目复杂在它需要去重！哈希法需要去重的细节很多，很不好做
看了Carl哥的讲解后，发现双指针的解法也在去重上有着诸多细节。
首先，先对原数组进行升序排序，这样负数在左侧，正数在右侧，采用i作为基底，left = i+1，right = nums.length-1，去寻找nums[i] + nums[left] + nums[right] = 0的三元组，若nums[i] + nums[left] + nums[right] > 0，则right往左移；若nums[i] + nums[left] + nums[right] < 0，则left往右移；若nums[i] + nums[left] + nums[right] = 0，则找到目标三元组
接下来就是剪枝，剪枝策略是，nums[i] > 0的时候，直接结束寻找，因为之后都为正数，凑不到三数相加等于0的情况
然后就是去重，当 nums[i] == nums[i-1]则continue，即对基底去重，不再收录重复的组合，这里操作了i-1，为了保证下标合法性，还要加上i>0的条件
最后收割答案的时候也要去重，当获得一个要求的三元组时，为了防止重复收割此三元组，在right>left的情况下，若nums[right-1] == nums[right]，则right--；同理，若nums[left] == nums[left+1]，则left++。注意使用while去重此情况，而不是if
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for(int i = 0;i < nums.length;i++){if(nums[i] > 0){return result;}if(i > 0 && nums[i] == nums[i-1]){continue;}int left = i + 1;int right = nums.length - 1;while(left < right){int sum = nums[i] + nums[left] + nums[right];if(sum > 0){right--;}else if(sum < 0){left++;}else{List<Integer> temp = new ArrayList<>();temp.add(nums[i]);temp.add(nums[left]);temp.add(nums[right]);result.add(temp);while(left < right && nums[left] == nums[left+1]){left++;}while(left < right && nums[right] == nums[right-1]){right--;}left++;right--;}}}return result;}
}
LeetCode18 四数之和
题目链接：https://leetcode.cn/problems/4sum/description/
文章讲解：https://programmercarl.com/0018.四数之和.html
视频讲解：https://www.bilibili.com/video/BV1DS4y147US/?vd_source=b989f2b109eb3b17e8178154a7de7a51
这题沿用三数之和那题的思路，只是外面多了一层for循环，且剪枝策略有所变化
先对nums数组进行升序排序，然后两层for循环找k和i，里面再设置left和right。当 nums[k] + nums[i] + nums[left] + nums[right] > target 时，right左移；当 nums[k] + nums[i] + nums[left] + nums[right] < target 时，left右移；当 nums[k] + nums[i] + nums[left] + nums[right] = target时，收割结果集
这题的剪枝策略是，当 nums[k] > target 且 nums[k] >= 0 时，结束最外层k循环；当 nums[k] + nums[i] > target && nums[k] + nums[i] >= 0 时，结束第二层i循环
去重策略是，当 nums[k] == nums[k-1] 则continue，即对基底k去重，不再收录重复的组合，这里操作了k-1，为了保证下标合法性，还要加上k>0的条件；同样的，当 nums[i] == nums[i-1]则continue，即对基底i去重，不再收录重复的组合，这里操作了i-1，为了保证下标合法性，还要加上i>k+1的条件
最后收割答案的时候也要记得去重，当获得一个要求的四元组时，为了防止重复收割此元组，在right>left的情况下，若nums[right-1] == nums[right]，则right--；同理，若nums[left] == nums[left+1]，则left++。注意使用while去重此情况，而不是if
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for(int k = 0; k < nums.length; k++){if(nums[k] > target && nums[k] >= 0){break;}if(k > 0 && nums[k] == nums[k-1]){continue;}for(int i = k+1; i < nums.length; i++){if(nums[k] + nums[i] > target && nums[k] + nums[i] >= 0){break;}if(i > k+1 && nums[i] == nums[i-1]){continue;}int left = i + 1;int right = nums.length - 1;while(left < right){long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];if(sum > target){right--;}else if(sum < target){left++; }else{List<Integer> temp = new ArrayList<>();temp.add(nums[k]);temp.add(nums[i]);temp.add(nums[left]);temp.add(nums[right]);result.add(temp);while(left < right && nums[left] == nums[left+1]){left++;}while(left < right && nums[right] == nums[right-1]){right--;}left++;right--;}}}}return result;}
}