四數相加

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

這個題注意它只需要給出次數，而不是元組。所以我們可以分治。將前兩個數組的加和情況使用map存儲起來，再將后兩個數組的加和情況使用map存儲起來，key存和，value存出現的次數。得到兩個map之后，我們遍歷其中一個map， 看另一個map中是否有和為0的情況，有就相加value，最后接可以得出答案。

在這種思路的基礎上，我們可以繼續優化代碼，例如我們在統計后兩個數組的同時，就已經可以將需要的和在前兩個數組的map中找出來，然后把次數進行相加。

代碼如下：

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {Map<Integer,Integer> records = new HashMap<>();for(int i = 0;i < nums1.length;i++) {for(int j = 0;j < nums2.length;j++) {records.put(nums1[i] + nums2[j],records.getOrDefault(nums1[i] + nums2[j],0) + 1);}}int result = 0;for(int i = 0;i < nums3.length;i++) {for(int j = 0;j < nums4.length;j++) {Integer count = records.get(0 - nums3[i] - nums4[j]);if(count != null) result += count;}}return result;}
}

贖金信

題目鏈接：383. 贖金信

二十六個字母，計數，第一反應就要想到數組。解題思路如下：

• 用數組統計第一個單詞的個數
• 然后遍歷第二個單詞，在數組中相應位置進行減法運算
• 遍歷數組
  • 如果存在大于0的數返回false
  • 不存在則返回true

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] records = new int[26];for (int i = 0; i < ransomNote.length(); i++) records[ransomNote.charAt(i) - 'a']++;for (int i = 0; i < magazine.length(); i++) records[magazine.charAt(i) - 'a']--;for (int i = 0; i < records.length; i++) if(records[i] > 0 ) return false;return true;}
}

三數之和

題目鏈接：15. 三數之和

解題思路：

看到這一題我們肯定會不自覺地拿它和兩數之和進行比較，我們是否能借助兩數之和的思想來完成這一題？首先我們回顧一下兩數之和的思想。在兩數之和中，我們是遍歷數組，每遍歷一個元素，就看target - 該元素 是否已經出現過（也就是是否在hash表中），如果在直接返回，如果不在就把這個元素添加到hash表中，代表該元素出現過，為后面的元素服務。

在三數相加中，我們嘗試沿用這種思路（先不直接到位，后面還會添加新邏輯）：

• 使用雙層for循環遍歷數組，外層循環相當于固定一個數，內層for循環沿用兩數相加的邏輯
• 初始化一個hashset，用來存已經存在的數，外層循環的以固定值不需要存
• 內存循環遍歷數組，尋找0 - nums[head]- nums[end] 是否存在于hashset中
• 如果存在那么該數組添加到答案列表中
• 如果不存在繼續遍歷
• 外層循環每完成一次清空set
• 最后返回答案集合

代碼如下：

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();HashSet<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {int need = -nums[i] - nums[j];if (set.contains(need)) {result.add(Arrays.asList(nums[i], nums[j], need));} else {set.add(nums[j]);}}set.clear();}return result;}
}

這個代碼完成了基本的功能但是還差本題的一個重點那就是去重。

就比如題目的這個用例：[-1,0,1,2,-1,-4]
如下兩種情況就會重復：

• i指向-1，j指向1，set里有0，這組會返回
• i指向0，j指向-1，set里有1，這組也會返回

我們可以嘗試排序解決這個問題：

排序之后還是這個用例就變為：[-4,-1,-1,0,1,2]

外層循環在固定到兩個-1的時候肯定會發生重復，所以我們可以添加一個條件，外層循環固定的數字和上一次相同時直接跳過：

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> result = new ArrayList<>();HashSet<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}for (int j = i + 1; j < nums.length; j++) {int need = -nums[i] - nums[j];if (set.contains(need)) {result.add(Arrays.asList(nums[i], nums[j], need));} else {set.add(nums[j]);}}set.clear();}return result;}
}

改完之后發現這個測試用例過不了：

原因就是當內層的兩數相加滿足之后，內層的下一次循環還是相同的數，那么相當于把這一組答案又加了一遍，那么我們針對這個情況進行改進：

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> result = new ArrayList<>();HashSet<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}Integer flag = null;for (int j = i + 1; j < nums.length; j++) {if(Integer.valueOf(nums[j]).equals(flag)) continue;flag = null;int need = -nums[i] - nums[j];if (set.contains(need)) {result.add(Arrays.asList(nums[i], nums[j], need));flag = nums[j];} else {set.add(nums[j]);}}set.clear();}return result;}
}

我們最后總結一下這道題：
這道題在沿用了我們前面兩數之和的思想之后，會存在一個去重問題：

• 外層重復：也就是當外層循環固定的數字和上一次相同時此次循環直接跳過
• 內層重復：也就是當內層的兩數相加滿足之后，內層的下一次循環還是相同的數。這個時候我們可以在每次三數之和滿足條件之后，將內層此次的值記錄一下，相鄰的下一次循環與此次的值一樣就跳過此次內循環。

當然此題也可以使用雙指針法來做，邏輯上更為簡單，代碼在此處不多做贅述。

四數之和

題目鏈接：18. 四數之和

這題使用雙指針法進行解題：

• 將數組進行排序
• 首先使用兩層的嵌套循環，固定兩個數
• 然后再使用雙指針left、right確定最后兩個數
• 將四個數字相加
  • 如果大于目標，right指針左移
  • 如果小于目標，left指針右移
  • 如果達到目標，left指針右移，right指針左移

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> result = new ArrayList<>();for(int i = 0;i < nums.length;i++) {for(int j = i + 1;j < nums.length;j++) {int left = j + 1;int right = nums.length - 1;while(left < right && left < nums.length) {int sum = 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--]));}}}}return result;}
}

接下來進行去重：

發生這種情況就是因為外層的雙層循環固定的兩個數字重復，我們添加去重的代碼：

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> result = new ArrayList<>();for(int i = 0;i < nums.length;i++) {if (i > 0 && nums[i] == nums[i - 1]) continue;for(int j = i + 1;j < nums.length;j++) {if (j > i + 1 && nums[j] == nums[j - 1]) continue;int left = j + 1;int right = nums.length - 1;while(left < right && left < nums.length) {int sum = 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--]));}}}}return result;}
}

這個去重的邏輯就是：

• if (i > 0 && nums[i] == nums[i - 1]) continue; 因為數組是按大小排序的，如果第一個固定的數不變，那么其他三個數不管怎么樣，都只會與target相等（這個情況已經存在需要去重）或者比target大，所以這個循環可以直接跳過
• if (j > i + 1 && nums[j] == nums[j - 1]) continue;邏輯類似

執行之后有一個測試樣例還是沒過：

造成這個情況的原因是因為，左右指針同時內縮的時候如果元素不變也會發生重復，我們繼續往里面添加去重邏輯:

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> result = new ArrayList<>();for(int i = 0;i < nums.length;i++) {if (i > 0 && nums[i] == nums[i - 1]) continue;for(int j = i + 1;j < nums.length;j++) {if (j > i + 1 && nums[j] == nums[j - 1]) continue;int left = j + 1;int right = nums.length - 1;while(left < right && left < nums.length) {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]));while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;left++;right--;}}}}return result;}
}

注意：測試用例中有一個例子考察的是四數相加的范圍超出了int的最大表達值，所以四數相加的和sum要使用long來存儲