代码随想录算法训练营| 454.四数相加II 、 383. 赎金信、 15. 三数之和、 18. 四数之和

454.四数相加II

题目

参考文章

思路：设置一个map，用于存储nums1和nums2中相加的和的值以及出现的次数，因为由题目可以知道a+b+c+d=0，即a+b=0-(c+d)，所以遍历nums3和nums4时，看看其中元素的和是否在map中出现过（即0-c-d是否出现过），如果出现过，则用一个变量res存储map中对应的value（假设因为nums1和nums2中的和有2个相同的，与nums3和nums4中的某个和相加为零，故有2个元组匹配了）

代码：

java">class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res=0;Map<Integer,Integer> map=new HashMap<Integer,Integer>();//统计num1 num2数组的和，以及次数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;}
}

383. 赎金信

题目

参考文章

思路：由题目意思可以知道，magazine中的元素可以组成ransomNote中的元素，而且magazine中的字符每个只能使用一次，也都是小写字母。所以这题如果当ransomNote的长度大于magazine时，直接返回false即可。然后定义一个record数组用于记录字符出现的次数，先遍历magazine字符串中的字符每次+1，然后遍历ransomNote中的字符每次-1。最后遍历这个record数组，如果其中某个数值小于零，则表示ransoomNote有个别元素不由magazine中的元素组成，返回false，最后如果都正常则返回true

代码：

java">class Solution {public boolean canConstruct(String ransomNote, String magazine) {if(ransomNote.length()>magazine.length()){return false;}int[] record=new int[26];for(char c:magazine.toCharArray()){record[c-'a']+=1;}for(char c:ransomNote.toCharArray()){record[c-'a']-=1;}for(int i:record){if(i<0){return false;}}return true;}
}

15. 三数之和

题目

参考文章

思路：本题运用二维数组+双指针的做法。因为题目是找一个数组中三个数的和，而且同一个位置的数不能重复出现（就是题目中的i，j，k三个位置），但是不同位置的数值可以重复。

首先，把二维数组排序，为了后面方便运用双指针。排序后，遍历数组，如果nums[i]>0了，就直接返回result即可，因为数组已经排序，后面的值已经没有意义了；如果当前num[i]的值和nums[i-1]相等，表示当前值和之前获取到的nums[i]值重复了，不符合题目要求，所以直接过滤掉这一次的循环。如上两次步骤做好后，就是定义left和right双指针了，用于三个数相加；用while循环，前提是right一定得大于left，但不能等于，等于的时候，right和left的值就重复了，不符合题意了；定义一个sum，存储三个值的和，当sum>0时，表示值过大，把right--，减小数值继续循环，当sum<0时，表示数值过小，把left++，增大数值继续循环；当sum==0时，就把对应的这三个值存储到二维数组result中，然后缩小双指针的范围即left++，right-- （前提是left和right已经去重的情况下，之后会写道）；到了这里就是最重要的一步，前面已经把nums[i]的值去重了，这里就要把nums[left],nums[right]的值也要去重，因为left是前进的，right是后退的，所以当nums[right]==nums[right-1]时，right--，过滤掉下一个要加的nums[right]值，同理left则是当nums[left]==nums[left+1]时，left++。

代码：

java">class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);//找a+b+c的和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(right>left){int sum=nums[i]+nums[left]+nums[right];if(sum>0){right--;}else if(sum<0){left++;}else{result.add(Arrays.asList(nums[i],nums[left],nums[right]));while(right>left&& nums[right]==nums[right-1])  right--;while(right>left && nums[left]==nums[left+1]) left++;right--;left++;}}}return result;}
}

18. 四数之和

题目

参考文章

思路：此题的思路和15题的三数之和思路差不多，只是i循环外再嵌套了一层k循环，多加了个参数target，所以再加一个剪枝操作即可（其实15题也用了剪枝操作，只是少了target的比较）。这个剪枝操作出来判断当前值是否大于零外，还要判断这个值是否大于target，如果不大于target也是不用剪枝的；去重原理与15题一致。然后到 i 层循环，这个时候，因为 i 层循环外已经嵌套了k层循环，所以i的值要从i=k+1开始，而剪枝操作要以 nums[k]+nums[i]为依据；然后去重发生了些许变化，因为 i 从k+1开始，所以要当i>k+1时判断去重，后面的双指针就完全和15题一样了，就不多赘述了哈

代码：

java">class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);  // 排序数组List<List<Integer>> result = new ArrayList<>();  // 结果集for(int k=0;k<nums.length;k++){//剪枝操作if(nums[k]>target&& nums[k]>=0){ //表示已经不符合题目要求了，直接退出循环，前提是nums[k]>0break;}//去重操作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){ //因为这里是从k上继承下来的，所以要加上k下表下的值进行剪枝break;}if(i>k+1&&nums[i]==nums[i-1]){continue;}int left=i+1;int right=nums.length-1;while(right>left){long sum=(long) nums[k]+nums[i]+nums[left]+nums[right];if(sum>target){right--;}else if(sum<target){left++;}else{result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));while(right>left&&nums[right]==nums[right-1]) right--;while(right>left&&nums[left]==nums[left+1]) left++;right--;left++;}}}}return result;}public static void main(String[] args) {Solution solution = new Solution();int[] nums = {1, 0, -1, 0, -2, 2};int target = 0;List<List<Integer>> results = solution.fourSum(nums, target);for (List<Integer> result : results) {System.out.println(result);}}
}