建设网站好难,大方做网站,wordpress 3.0,网站的详情页面454.四数相加 题目链接#xff1a;454. 四数相加 II - 力扣#xff08;LeetCode#xff09; 视频/文档链接#xff1a;代码随想录 (programmercarl.com) 第一想法
遍历数组num1,num2#xff0c;计算其和出现的数量#xff0c;放入map集合中#xff0c;键为和#xff0…454.四数相加 题目链接454. 四数相加 II - 力扣LeetCode 视频/文档链接代码随想录 (programmercarl.com) 第一想法
遍历数组num1,num2计算其和出现的数量放入map集合中键为和值为出现的次数。遍历num3num4,0-若其和的值出现在Map集合中则count该值即可。
可优化点
不熟悉调用mapAPI。
map.put(sum, map.getOrDefault(sum, 0) 1);
res map.getOrDefault(0 - i - j, 0);
代码
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int count 0;MapInteger, Integer map new HashMapInteger, Integer();for(int i : nums1){for(int j:nums2){int sum ij;map.put(sum,map.getOrDefault(sum,0)1);}}for (int k : nums3) {for (int n : nums4) {int sum kn;if(map.containsKey(-sum)){countmap.get(-sum);}}}return count;}
}
383.赎金信 题目链接383. 赎金信 - 力扣LeetCode 视频/文档链接代码随想录 (programmercarl.com) 第一想法
这个题和力扣242题很像。
对于案例ransomNote aa, magazine aab
力扣242字符串s和t每个字母出现的次数都必须一样。所以返回false
力扣383只要求ransdomNote每个字母数量magazine则返回true。
代码
一次过。
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] ransdomArr new int[26];int[] magazineArr new int[26];for (int i 0; i ransomNote.length(); i) {ransdomArr[ransomNote.charAt(i)-a];}for (int j 0; j magazine.length(); j) {magazineArr[magazine.charAt(j)-a];}for (int i 0; i 26; i) {if(ransdomArr[i]magazineArr[i])return false;}return true;}
}
15.三数之和 题目链接15. 三数之和 - 力扣LeetCode 文档/视频链接代码随想录 (programmercarl.com) 第一想法
abc 0,直接暴力循环然后去重。 a从第1个元素遍历b从i1处遍历然后c的值应为-ab,看map集合中是否存在。最终去除重复元素。
代码随想录想法
首先先将数组排序一层for循环i代表当前元素a再定义left指针b和right指针c
若相加之和0,则right--相加之和0,left相加之和 0则加入结果集。直到left right终止循环相等时无意义。
当去重a时需要判断 if(nums[i] ! nums[i-1])即当前元素与之前元素不同那么第一个元素不是会报空指针异常么怎么避免这个问题按照这样就能避免对 i 0 时进行判定了。 if (i 0 nums[i] nums[i - 1]) { // 去重acontinue;}每次遍历对第一个元素要都判断是否0所以nums[i]0这个判断逻辑要加到循环里面。还有个细节是直接return而不是continue了。因为已经排序的数组一旦碰上正数往后的也必须是正数。
关于b和c的去重
我在看视频的时候也想的是直接将去重逻辑提前。 if (nums[i] nums[left] nums[right] 0) { right--; // 去重 right while (left right nums[right] nums[right 1]) right--; } else if (nums[i] nums[left] nums[right] 0) { left; // 去重 left while (left right nums[left] nums[left - 1]) left; } else { }
但对提升效率没有帮助反正去重也是一个一个减下去在哪里减都是一样的。
索性放在else中结构更好看一点。
同时去重时还要判断leftright是为了防止指针越界需要加上。可以记小模版就是whileleftright再套while循环里面while条件要考虑加外层循环条件。
代码
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger endResult new ArrayList();Arrays.sort(nums);//排序for (int i 0; i nums.length; i) {if(nums[i]0)return endResult;if(i0nums[i]nums[i-1])continue;//进入判断逻辑int left i 1;int right nums.length - 1;while (left right){if(nums[i]nums[left]nums[right]0)right--;else if(nums[i]nums[left]nums[right]0)left;else{//将结果加入endResult中,这个语句是这样写的。endResult.add(Arrays.asList(nums[i],nums[left],nums[right]));//这里就需要去重了while (leftrightnums[right-1]nums[right])right--;//假设233,循环结束后right指的是最后一个重复元素3(第2个)while (leftrightnums[left1]nums[left])left;//同理right--;//这里才正真跳到最终不同的值上left;}}}return endResult;}
}
18.四数之和 题目链接/文章讲解/视频讲解 代码随想录 在三数之和基础上再套一层循环。
看完代码随想录的想法
剪枝的逻辑不能是nums[i]0因为此时目标是target而target可能是负数排序之后的数组可以是越加越小即target -5 nums [-4,-1,0,0]。 但是我们依旧可以去做剪枝逻辑变成nums[i] target (nums[i] 0 || target 0)就可以了。 每次对第一个元素不做判断所以第二层循环去重时ji1nums[j]nums[j-1],而不应当惯性思维是j0
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger endResult new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length; i) {//剪枝if(nums[i]target(nums[i]0||target0))return endResult;if(i0nums[i]nums[i-1])continue;for (int j i 1; j nums.length - 1 - 1; j) { //0,1,2,3j2,//去重if( j i1 nums[j] nums [j-1]) //j为1时不应去重continue;int left j1;int right nums.length-1;while (leftright){if(nums[i]nums[j]nums[left]nums[right]target)right--;else if(nums[i]nums[j]nums[left]nums[right]target)left;else{endResult.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while (leftrightnums[right-1] nums[right])right--;while (leftrightnums[left1] nums[left])left;right--;left;}}}}return endResult;}
}
