代码随想录算法训练营第7天

454.四数相加

题目链接：454. 四数相加 II - 力扣（LeetCode）

视频/文档链接：代码随想录 (programmercarl.com)

第一想法

遍历数组num1,num2，计算其和出现的数量，放入map集合中，键为和，值为出现的次数。遍历num3，num4,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;Map<Integer, Integer> map = new HashMap<Integer, Integer>();for(int i : nums1){for(int j:nums2){int sum = i+j;map.put(sum,map.getOrDefault(sum,0)+1);}}for (int k : nums3) {for (int n : nums4) {int sum = k+n;if(map.containsKey(-sum)){count+=map.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)

第一想法

a+b+c = 0,直接暴力循环然后去重。
a从第1个元素遍历，b从i+1处遍历，然后c的值应为-（a+b）,看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中，结构更好看一点。

同时去重时还要判断left<right，是为了防止指针越界需要加上。可以记小模版就是while（left<right）再套while循环，里面while条件要考虑加外层循环条件。

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> endResult = new ArrayList<>();Arrays.sort(nums);//排序for (int i = 0; i < nums.length; i++) {if(nums[i]>0)return endResult;if(i>0&&nums[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 (left<right&&nums[right-1]==nums[right])right--;//假设2，3，3,循环结束后right指的是最后一个重复元素3(第2个)while (left<right&&nums[left+1]==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)就可以了。

 每次对第一个元素不做判断，所以第二层循环去重时j>i+1&&nums[j]==nums[j-1],而不应当惯性思维是j>0

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> endResult = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {//剪枝if(nums[i]>target&&(nums[i]>0||target>0))return endResult;if(i>0&&nums[i]==nums[i-1])continue;for (int j = i + 1; j < nums.length - 1 - 1; j++) { //0,1,2,3，j<2,//去重if( j > i+1 &&nums[j] == nums [j-1]) //j为1时不应去重continue;int left = j+1;int right = nums.length-1;while (left<right){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 (left<right&&nums[right-1] ==nums[right])right--;while (left<right&&nums[left+1] == nums[left])left++;right--;left++;}}}}return endResult;}
}