代码随想录Day07
lc454
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer,Integer> abmap=new HashMap<>(); for (int i = 0; i < nums1.length; i++) { for (int j = 0; j < nums2.length; j++) { if (!abmap.containsKey(nums1[i]+nums2[j])){ abmap.put(nums1[i]+nums2[j],1); }else{ Integer integer = abmap.get(nums1[i] + nums2[j]); integer++; abmap.put(nums1[i] + nums2[j],integer); } } } int count=0; for (int i = 0; i < nums3.length; i++) { for (int j = 0; j < nums4.length; j++) { if (abmap.containsKey(-nums3[i] - nums4[j])){ count+=abmap.get(-nums3[i] - nums4[j]); } } } return count; } }
lc383
class Solution { public boolean canConstruct(String ransomNote, String magazine) { if (magazine.length() < ransomNote.length()) { return false; } Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < ransomNote.length(); i++) { char ran = ransomNote.charAt(i); map.put(ran, map.getOrDefault(ran, 0) + 1); } for (int i = 0; i < magazine.length(); i++) { char c = magazine.charAt(i); if (map.containsKey(c)) { if (map.get(c) <= 0) { continue; } else { map.put(c, map.get(c) - 1); } } } for (int count : map.values()) { if (count > 0) { return false; } } return true; } }
lc15
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> list=new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (nums[i]>0){ return list; } if (i>0 && nums[i]==nums[i-1]){ continue; } int left=i+1; int right= nums.length-1; while (left<right){ int sum=nums[i]+nums[left]+nums[right]; if (sum>0){ right--; }else if (sum<0){ left++; }else{ list.add(Arrays.asList(nums[i],nums[left],nums[right])); //执行去重逻辑 while (left<right && nums[right]==nums[right-1]){ right--; } while (left<right && nums[left]==nums[left+1]){ left++; } right--; left++; } } } return list; } }
lc18
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { // nums[i] > target 直接返回, 剪枝操作 if (nums[i] > 0 && nums[i] > target) { return result; } if (i > 0 && nums[i - 1] == nums[i]) { // 对nums[i]去重 continue; } for (int j = i + 1; j < nums.length; j++) { if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重 continue; } int left = j + 1; int right = nums.length - 1; while (right > left) { // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出 long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); // 对nums[left]和nums[right]去重 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; left++; right--; } } } } return result; } }