454. 四數相加 II

給你四個整數數組 nums1、nums2、nums3 和 nums4 ，數組長度都是 n ，請你計算有多少個元組 (i, j, k, l) 能滿足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

輸入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
輸出：2
解釋：
兩個元組如下：

1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

class Solution {public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();for (int u : A) {for (int v : B) {countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);}}int ans = 0;for (int u : C) {for (int v : D) {if (countAB.containsKey(-u - v)) {ans += countAB.get(-u - v);}}}return ans;}
}

這段代碼定義了一個名為 Solution 的類，其中包含一個方法 fourSumCount。這個方法用于解決四數之和問題：給定四個整數數組 A, B, C, 和 D，計算有多少個由一個來自 A 和一個來自 B 的數以及一個來自 C 和一個來自 D 的數構成的四元組，它們的和為 0。

邏輯分析：

1. 初始化哈希表（Map）：首先，創建一個哈希表 countAB 用于存儲數組 A 和 B 中元素兩兩兩兩數之和的頻次。鍵為和的值，值為該和出現的次數。

2. 計算 A 和 B 的組合和：遍歷數組 A 和 B 中的所有元素，計算它們的和，并在哈希表 countAB 中累積這些和的計數，使用 getOrDefault 方法來簡化計數累加邏輯，如果鍵不存在則默認值為0，然后加1。

3. 計算四數和為0的組合數：接著，遍歷數組 C 和 D 的元素，對于每一對 u 和 v，檢查 countAB 是否包含 -u - v 這個鍵（即如果存在一個來自 A 和 B 的和與 u 和 v 之和為相反數），如果存在，則累加該和在 countAB 中的頻次到答案 ans。

4. 返回結果：最后，返回累計的滿足條件的四數之和為0的組合總數 ans。

代碼特點與優化：

• 空間換時間：通過預計算 A 和 B 的所有組合和及其頻次，將原本需要四重循環的問題轉換為兩重循環加上查找，顯著提高了效率。
• 哈希表（Map）使用：利用哈希表的高效查找特性，簡化了尋找特定和的操作，從原本可能的線性查找降為接近常數時間。
• 代碼簡潔性：雖然邏輯清晰，但在實際應用中可能還需考慮邊界條件處理（如輸入數組長度為0的情況），以及優化點（如適當處理大數以避免溢出問題）。

綜上所述，這段代碼提供了一種有效且相對高效求解四數之和為0的組合數目的方法，體現了哈希表在優化搜索問題中的應用。

383. 贖金信

給你兩個字符串：ransomNote 和 magazine ，判斷 ransomNote 能不能由 magazine 里面的字符構成。

如果可以，返回 true ；否則返回 false 。

magazine 中的每個字符只能在 ransomNote 中使用一次。

示例 1：

輸入：ransomNote = “a”, magazine = “b”
輸出：false
示例 2：

輸入：ransomNote = “aa”, magazine = “ab”
輸出：false
示例 3：

輸入：ransomNote = “aa”, magazine = “aab”
輸出：true

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

這段代碼定義了一個名為 Solution 的類，其中包含一個方法 canConstruct。這個方法用于判斷能否通過重新排列給定的雜志字符串 magazine 中的字符，來拼寫出勒索要贖金信字符串 ransomNote。如果可以，則返回 true；如果不可以，則返回 false。

邏輯分析：

1. 長度檢查：首先，進行一個簡單的長度檢查，如果贖金信的長度大于雜志字符串長度，顯然無法構造，直接返回 false。

2. 字符計數數組初始化：聲明一個長度為26的小寫英文字母表數組 cnt，用于計數雜志字符串中每個字符出現的次數。這里利用了小寫字母’a’到’z’在ASCII碼表中連續的特性，減去’a’后即可映射到數組的索引。

3. 計算雜志字符頻次：遍歷雜志字符串 magazine 的字符，逐個對應回字符在數組 cnt 中計數加1。利用了字符與其在ASCII碼的關系，減去 ‘a’ 來索引數組位置。

4. 檢查贖金信字符可用性：接著，遍歷贖金信 ransomNote 的字符，逐個檢查該字符在 cnt 數組中的計數是否足夠。如果有足夠的字符，就將計數減1；如果不夠（即計數小于0），說明該字符在雜志中數量不足，直接返回 false。

5. 返回結果：如果成功遍歷完贖金信所有字符且未返回，說明可以構造出來，最后返回 true。

代碼特點：

• 空間效率：使用固定大小的計數數組而非哈希表減少了空間消耗，因為只考慮了小寫字母，局限了字符范圍。
• 時間效率：兩重循環，時間復雜度為O(len(ransomNote) + len(magazine))，其中len表示字符串長度，因為分別遍歷了兩次字符串。
• 簡潔性：直接利用字符編碼特性進行索引映射，減少了額外的字符判斷和映射邏輯。

綜上所述，此方法通過直接計數字符頻次并檢查是否足夠來判斷是否能構造贖金信，是一種直觀且效率較高的實現方式。

15. 三數之和

給你一個整數數組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請

你返回所有和為 0 且不重復的三元組。

注意：答案中不可以包含重復的三元組。

示例 1：

輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。
示例 2：

輸入：nums = [0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為 0 。
示例 3：

輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為 0 。

class Solution {public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<List<Integer>>();// 枚舉 afor (int first = 0; first < n; ++first) {// 需要和上一次枚舉的數不相同if (first > 0 && nums[first] == nums[first - 1]) {continue;}// c 對應的指針初始指向數組的最右端int third = n - 1;int target = -nums[first];// 枚舉 bfor (int second = first + 1; second < n; ++second) {// 需要和上一次枚舉的數不相同if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}// 需要保證 b 的指針在 c 的指針的左側while (second < third && nums[second] + nums[third] > target) {--third;}// 如果指針重合，隨著 b 后續的增加// 就不會有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環if (second == third) {break;}if (nums[second] + nums[third] == target) {List<Integer> list = new ArrayList<Integer>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}
}

這段代碼是用于解決“三數之和”問題的Java實現，給定一個整數數組 nums，找出數組中所有和為0的三個數的組合，并返回這些組合的列表。以下是代碼的邏輯解析：

1. 初始化:

   • 首先對數組 nums 進行排序，便于后續的雙指針操作。
   • 初始化一個空的結果列表 ans，用于存儲滿足條件的三元組。

2. 外層循環枚舉 a:

   • 用變量 first 作為外層循環變量，從0遍歷到數組長度。

   • 避度處理重復值：若當前 first 不是第一個元素且與前一個元素值相同，則跳過，避免重復解。

   • 初始化 third 指針為數組最后一個元素，目標值 target 為 -nums[first]，以使 a + b + c = 0。

3. 中層循環枚舉 b:

   • 用變量 second 作為中層循環變量，從 first + 1 開始遍歷。
   • 處理重復值：若 second 不是 first + 1 且與前一個元素值相同，則跳過，避免重復解。
   • 維護 third 指針位置，使其滿足 nums[second] + nums[third] <= target，不斷向左移動直到符合條件或 second == third。
   • 若 second 與 third 重合，說明后續增加的 second 不可能再滿足條件，直接跳出循環。

4. 檢查并添加解:

   • 當 nums[second] + nums[third] == target 成立時，說明找到了一個解。
   • 將 nums[first], nums[second], nums[third] 加入臨時列表 list，然后將 list 添加到結果列表 ans 中。

5. 返回結果:

   • 遍歷完成后返回結果列表 ans。

這段代碼通過排序和雙指針技巧高效地解決了三數之和問題，時間復雜度主要受排序影響為O(nlogn)，空間復雜度為O(n)（最壞情況下存儲所有解）。注意，由于代碼中存在若干處邏輯錯誤（如循環更新語句末尾的 ++ 應替換為 ;），修正后才能正常運行。

18. 四數之和

給你一個由 n 個整數組成的數組 nums ，和一個目標值 target 。請你找出并返回滿足下述全部條件且不重復的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個四元組元素一一對應，則認為兩個四元組重復）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 返回答案 。

示例 1：

輸入：nums = [1,0,-1,0,-2,2], target = 0
輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：

輸入：nums = [2,2,2,2,2], target = 8
輸出：[[2,2,2,2]]

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();if (nums == null || nums.length < 4) {return quadruplets;}Arrays.sort(nums);int length = nums.length;for (int i = 0; i < length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}for (int j = i + 1; j < length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}int left = j + 1, right = length - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;} else if (sum < target) {left++;} else {right--;}}}}return quadruplets;}
}

這段代碼是一個Java實現，用于解決尋找數組中所有和為目標值的四數組合（4Sum）的問題。給定一個整數數組 nums 和一個目標整數 target，如果 nums 中存在四個元素 a, b, c, 和 d 使得 a + b + c + d 的和等于 target，那么找出所有這樣的四元組。返回一個二維列表，其中每個列表表示一個四元組。

解析代碼邏輯：

1. 初始化: 創建一個空的 quadruplets 列表，用于存放所有滿足條件的四元組。如果輸入數組為空或長度小于4，直接返回空列表。

2. 排序: 對 nums 進行排序，便于使用雙指針法減少搜索空間。

3. 三層循環:

   • 外層循環 (i): 遍歷數組，避免重復，若當前數與前一個相同則跳過。
   • 中層循環 (j): 從 i+1 開始，同樣避免重復，計算四個數之和的上下界，提前剪枝。
   • 雙指針法 (left, right): 在 j+1 和 length-1 之間，尋找另外兩個數，使得四數之和等于 target。若找到，添加四元組到結果列表并跳過重復值，否則根據和調整指針。

4. 返回結果: 最后返回所有滿足條件的四元組列表 quadruplets。

關鍵點:

• 排序 是基礎，使得雙指針法可行。
• 剪枝策略 減少不必要的循環，提高效率。
• 避免重復 通過跳過相同元素，確保結果唯一性。

注意：代碼中有部分地方需要修正以確保正確性，例如 quadruplets.add(Arrays.asList(...)) 應該為 quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]))。此外，確保所有邏輯分支和邊界條件正確處理。