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

454.四数相加II

四个数组分成两组进行for循环，先用HashMap存储所有第一组for循环出现的和的次数。再进行第二组for循环，每一次得出的和判断其负数是否在map的key中，如果存在，就加上这个value。

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();for(int num1:nums1){for(int num2:nums2){if(map.containsKey(num1+num2)){int a = map.get(num1+num2);map.put(num1+num2,++a);}else{map.put(num1+num2,1);}}}int total = 0;for(int num3:nums3){for(int num4:nums4){if(map.containsKey(-(num3+num4))){total += map.get(-(num3+num4));}}}return total;}
}

383. 赎金信

和有效的字母异位词那道题目类似

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record = new int[26];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 r:record){if(r < 0) return false;}return true;}
}

15. 三数之和

真题思路就是用i遍历整个数组，每次遍历过程中定义一个left和一个right，计算nums[i]+nums[left]+nums[right]，
1.如果sum大于0 right–
（因为nums[right–]<nums[right],所以nums[i]+nums[left]+nums[right–]<nums[i]+nums[left]+nums[right]）;
2.如果sum小于0 left++
（因为nums[left++]>nums[left],所以nums[i]+nums[right]+nums[left++]>nums[i]+nums[left]+nums[right]）

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> resList = new ArrayList<List<Integer>>();Arrays.sort(nums);if(nums[0] > 0 || nums[nums.length-1] < 0 || nums.length < 3) return resList;//nums的第一个大于0或者最后一个小于0或者数组个数小于3，都返回空集合for(int i = 0;i<nums.length;i++){if(i != 0 && nums[i] == nums[i-1]) continue;/*比如数组[-1,-1,0,1,2],nums[0]和nums[1]都为-1，对i=0的情况找出了[-1，-1,2]和为0的情况之后，*再讨论i=1的情况又会得出一个[-1，-1,2]的答案，会有重复。但是不能nums[i] == nums[i+1]这样向后对比，*因为nums[0]=nums[1]，直接跳过i=0，就忽略了[-1，-1,2]这种情况。*/int left = i+1;int right = nums.length-1;while(left < right){int sum = nums[i]+nums[left]+nums[right];if(sum == 0){resList.add(Arrays.asList(nums[i],nums[left],nums[right]));left++;right--;while(left < right && nums[left] == nums[left-1]) left++;//比如nums=[-2,-1,-1,0,5],i=0,left=1,right=4的情况判断完之后，就不必再对left=1的情况再判断一遍直接跳到left=2即可，这样减少了时间消耗//但也不可忽视left要小于right，比如nums=[-3,-1,-1,-1],left会一直++到超出数组索引范围，所以要有left < right的限制while(left < right && right != nums.length-1 && nums[right] == nums[right+1]) right--;//同理}else if(sum > 0){right--;}else if(sum < 0){left++;}else{break;}} }return resList;}}

18. 四数之和

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> listRes = new ArrayList<List<Integer>>();for(int i = 0;i < nums.length-3;i++){if(i != 0 && nums[i] == nums[i-1]) continue;//去重for(int j = i+1;j<nums.length-2;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] + (long)nums[j] + (long)nums[left] + (long)nums[right];if(sum==target){ArrayList<Integer> list = new ArrayList<Integer>();listRes.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));left++;right--;while(left < right && nums[left] == nums[left-1]) left++;//去重while(left < right && right != nums.length - 1 && nums[right] == nums[right+1]) //去重right--;}else if(sum>target){right--;}else{left++;}}}}return listRes;}
}