php网站建设招聘,网站开发与设计论文,手表网站大全,成都微信网站制作打卡Day7 1.454.四数相加II2.383. 赎金信3.15. 三数之和4.18. 四数之和 1.454.四数相加II
题目链接#xff1a;四数相加II 文档讲解#xff1a; 代码随想录
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res 0;Map… 打卡Day7 1.454.四数相加II2.383. 赎金信3.15. 三数之和4.18. 四数之和 1.454.四数相加II
题目链接四数相加II 文档讲解 代码随想录
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res 0;MapInteger,Integer map new HashMap();for(int i: nums1){for(int j: nums2){int sum i j;map.put(sum, map.getOrDefault(sum, 0) 1);}}for(int i: nums3){for(int j: nums4){res map.getOrDefault((0 - i - j), 0);}}return res;}
}2.383. 赎金信
题目链接赎金信 文档讲解 代码随想录
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record new int[26];if(ransomNote.length() magazine.length()){return false;}for(int i 0; i magazine.length(); i){record[magazine.charAt(i) - a];}for(int i 0; i ransomNote.length(); i){record[ransomNote.charAt(i) - a]--;}for(int i 0; i ransomNote.length(); i){//判断不等于0是不对的没有考虑到magazine中存在该字母出现更多次的情况if(record[ransomNote.charAt(i) - a] 0){return false;}}return true;}
}//使用增强for
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record new int[26];if(ransomNote.length() magazine.length()){return false;}for(char i: magazine.toCharArray()){record[i - a] 1;}for(char i: ransomNote.toCharArray()){record[i - a] - 1;}for(int i: record){if(i 0){return false;}}return true;}
}3.15. 三数之和
题目链接三数之和 文档讲解 代码随想录
class Solution {public ListListInteger threeSum(int[] nums) {//哈希法ListListInteger res new ArrayList();//需要对nums进行排序Arrays.sort(nums);for(int i 0; i nums.length; i){//如果第一个元素大于0则不可能存在三元组if(nums[i] 0){return res;}//a去重if(i 0 nums[i] nums[i - 1]){continue;}HashSetInteger set new HashSet();for(int j i 1; j nums.length; j){//b去重if(j i 2 nums[j] nums[j - 1] nums[j] nums[j - 2]){continue;}int c - nums[i] - nums[j];if(set.contains(c)){res.add(Arrays.asList(nums[i], nums[j], c));set.remove(c);//c去重}else{set.add(nums[j]);} }}return res;}
}注意点 1a 的去重在两种方法中纠结一是判断nums[i] nums[i1]一种是判断nums[i] nums[i-1]。如果前者那么存在遗漏情况例如{-1-12}。 2b 的去重可以和 a 一样判断nums[j] nums[j-1]从而跳过相同的b。但是这样子可能会遗漏情况例如{000}。因此只有当当前的 b 和前两个 b 都相同时才跳过当前的 b。这样可以保证至少有一个 b 被使用并且不会出现重复。
class Solution {public ListListInteger threeSum(int[] nums) {//双指针法ListListInteger res new ArrayList();//需要对nums进行排序Arrays.sort(nums);for(int i 0; i nums.length; i){if(nums[i] 0){return res;} //a去重if(i 1 nums[i] nums[i - 1]){continue;}int left i 1;int right nums.length - 1;while(left right){//left和right是两个指针与二分查找不一样int sum nums[i] nums[left] nums[right];if(sum 0){right--;}else if(sum 0){left;}else{res.add(Arrays.asList(nums[i], nums[left], nums[right]));//去重while(left right nums[left] nums[left 1]){left;}while(left right nums[right] nums[right - 1]){right--;}right--;left;}}} return res;}
}两数之和不能用双指针法的原因因为双指针法需要排序而两数之和需要返回索引下标。
4.18. 四数之和
题目链接四数之和 文档讲解 代码随想录
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger res new ArrayList();Arrays.sort(nums);for(int i 0; i nums.length; i){//剪枝if(nums[i] 0 nums[i] target){return res;}//去重if(i 0 nums[i] nums[i - 1]){continue;}for(int j i 1; j nums.length; j){ //去重if(j i 1 nums[j] nums[j - 1]){continue;}int left j 1;int right nums.length - 1;while(left right){long sum (long) nums[i] nums[j] nums[left] nums[right];//防止溢出if(sum target){right--;}else if(sum target){left;}else{res.add(Arrays.asList(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 res;}
}
