【leetcode】第三章 哈希表part02

454.四数相加II

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {HashMap<Integer,Integer> map = new HashMap<>();// 统计频率for (int i = 0; i < nums1.length; i++) {for (int j = 0; j < nums2.length; j++) {int num = nums1[i] + nums2[j];map.put(num,map.getOrDefault(num,0)+1);}}int cnt = 0;for (int i = 0; i < nums3.length; i++) {for (int j = 0; j < nums4.length; j++) {int restNum = nums3[i] + nums4[j];if (map.containsKey(-restNum)) {cnt += map.get(-restNum);}}}return cnt;
}

383. 赎金信

• 使用map方法

public boolean canConstruct(String ransomNote, String magazine) {// ransomNote是magazine的子串// aa aabcdeaHashMap<Character,Integer> map = new HashMap<>();for (char c : ransomNote.toCharArray()) {map.put(c,map.getOrDefault(c,0)+1);}for (int i = 0; i < magazine.length(); i++) {char ch = magazine.charAt(i);if (map.containsKey(ch)) {map.put(ch,map.get(ch)-1);}}// 判断for (Integer cnt : map.values()) {if (cnt > 0) return false;}return true;}

• 使用数组方法

public boolean canConstruct(String ransomNote, String magazine) {// ransomNote是magazine的子串// aa abint[] hash = new int[26];for (int i = 0; i < magazine.length(); i++) {char ch = magazine.charAt(i);hash[ch-'a']++;}for (int i = 0; i < ransomNote.length(); i++) {char c  = ransomNote.charAt(i);hash[c-'a']--;if (hash[c-'a'] < 0) {return false;}}return true;}

15 三数之和

public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for (int i = 0; i < nums.length-2; i++) {if (nums[i] > 0) break;if (i != 0 && nums[i] == nums[i-1]) {continue;}int left = i + 1;int right = nums.length-1;while (left < right) {int target = nums[i] + nums[left] + nums[right];if (target == 0) {res.add(Arrays.asList(nums[i],nums[left],nums[right]));while (left < right && nums[left] == nums[left+1]) left++;while (left < right && nums[right] == nums[right-1]) right--;left++;right--;}else if (target < 0) {left++;}else {right--;}}}return res;
}

18. 四数之和

public List<List<Integer>> fourSum(int[] nums, int target) {// 输入：nums = [1,0,-1,0,-2,2], target = 0//输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length-3; i++) {// // 剪枝if (nums[i] > target && target >= 0) return res;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 num = (long)nums[i] + nums[j] + nums[left] + nums[right];if (num == target) {res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while (left < right && nums[left] == nums[left+1]) left++;while (left < right && nums[right] == nums[right-1]) right--;left++;right--;}else if (num < target) {left++;}else {right--;}}}}return res;
}