454. 四數相加II

題目鏈接：454. 四數相加II

思路：哈希法。使用map集合，key存放a+b的值，value存放a+b出現的次數。使用兩層循環，循環前兩個數組，找出a+b，對map賦值。再用兩層循環，遍歷后兩個數組，找出符合map中符合目標的值，并通過value獲取出現的次數并累加。（其實就是將四數相加變成兩數相加，將時間復雜度從O(n4)降至O(n2)）

時間復雜度：O(n2)

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int count = 0;    // 統計a+b+c+d = 0 出現的次數Map<Integer, Integer> map = new HashMap<>();// 先遍歷前兩個數組，將a+b以及出現的次數放到map中for (int a : nums1) {for (int b : nums2) {map.put(a + b, map.getOrDefault(a + b, 0) + 1);}}// 然后遍歷后兩個數組，從map中找到符合條件的a+b并計數for (int c : nums3) {for (int d : nums4) {if (map.containsKey(0 - (c + d))) {count += map.get(0 - (c + d));}}}return count;}
}

---

383. 贖金信

題目鏈接：383. 贖金信

思路：哈希法。其實就是字母異位詞的擴展題目，思路同字母異位詞。

時間復雜度：O(n)

class Solution {public boolean canConstruct(String ransomNote, String magazine) {// 變向的字母異位詞int[] count = new int[26];for (int i = 0; i < ransomNote.length(); i++) {count[ransomNote.charAt(i) - 'a']++;}for (int i = 0; i < magazine.length(); i++) {count[magazine.charAt(i) - 'a']--;}for (int i : count) {if (i > 0) {   // 僅在此處有差別return false;}}return true;}
}

---

15. 三數之和

題目鏈接：15. 三數之和

思路：使用雙指針法。（本題的重點在于考察去重操作。）先對數組進行排序。使用i遍歷一遍數組，遍歷過程中，left初始為i+1，right初始為最后一個元素，然后如果left和right指向的元素符合目標值，將三個數放進結果中；如果不符合目標值，調整left和right的位置。

注意：要對三個數都進行去重操作。

i指向的是a，如果和前一個元素重復，就沒必要再進行遍歷了，跳過執行下一個元素。

left指向的是b，如果存入結果后，后一個元素仍然和當前元素相同，跳過后一個元素。

right指向的是c，如果存入結果后，前一個元素仍然和當前元素相同，跳過前一個元素。

通過雙指針將時間復雜度由O(n3)降至了O(n2)

時間復雜度：O(n2)

class Solution {public List<List<Integer>> threeSum(int[] nums) {// 雙指針法List<List<Integer>> res = new LinkedList<>();// 先進行排序Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {// 如果當前最小的元素都大于0了，返回res就可以了if (nums[i] > 0) return res;// 對a去重，如果和前一個元素相同，說明已經判斷過了，執行下一個if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1, right = nums.length - 1;while (left < right) {if (nums[i] + nums[left] + nums[right] < 0) {left++;} else if (nums[i] + nums[left] + nums[right] > 0) {right--;} else {res.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) { // 對b去重left++;}while (left < right && nums[right] == nums[right - 1]) { // 對c去重right--;}left++;right--;}}}return res;}
}

---

8. 四數之和

題目鏈接：8. 四數之和

思路：使用雙指針法，原理同三數之和。因為這次目標值可以指定為負數，所以要注意剪枝時的操作。用i和j確定a和b，用left和right尋找符合條件c和d。（同樣要注意，這四個數，每個數都要進行去重操作。）

不要判斷nums[k] > target 就返回了，三數之和 可以通過 nums[i] > 0 就返回了，因為 0 已經是確定的數了，四數之和這道題目 target是任意值。比如：數組是[-4, -3, -2, -1]，target是-10，不能因為-4 > -10而跳過。但是我們依舊可以去做剪枝，邏輯變成nums[i] > target && (nums[i] >= 0 || target >= 0)就可以了。

四數之和的雙指針解法是兩層for循環nums[k] + nums[i]為確定值，依然是循環內有left和right下標作為雙指針，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情況。

那么一樣的道理，五數之和、六數之和等等都采用這種解法。

時間復雜度：O(n3)

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {// 雙指針法，類似三數之和List<List<Integer>> res = new LinkedList<>();// 先排序Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {if (nums[i] > target && (nums[i] >= 0 || target >= 0)){// 剪枝操作return res;}if (i > 0 && nums[i] == nums[i - 1]) { // 對a去重continue;}for (int j = i + 1; j < nums.length; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) // 對b去重continue;int left = j + 1, right = nums.length - 1;while (left < right) {if (nums[i] + nums[j] + nums[left] + nums[right] < target) {left++;} else if (nums[i] + nums[j] + nums[left] + nums[right] > target) {right--;} else {res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) {// 對c去重left++;}while (left < right && nums[right] == nums[right - 1]) {// 對d去重right--;}left++;right--;}}}}return res;}
}

---

哈希表題目總結

從哈希表的理論基礎到數組、set和map的經典應用，把哈希表的全貌呈現出來。

同時也強調雖然map是萬能的，詳細介紹了什么時候用數組，什么時候用set。

相信通過代碼隨想錄中的哈希表總結篇，大家可以對哈希表有一個全面的了解。

---