1. 問題背景

在算法面試和編程練習中，**兩數之和（Two Sum）和三數之和（3Sum）**是兩個經典的數組處理問題。這兩個問題不僅是檢驗基礎算法能力的試金石，也是理解高效搜索技巧的重要案例。本文將通過Java代碼實現這兩個問題，并深入解析其優化思路。

---

2. 兩數之和（Two Sum）

2.1 問題描述

1. 兩數之和

2.2 哈希表解法

代碼實現

import java.util.HashMap;
import java.util.Map;public class TwoSum {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> numMap = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (numMap.containsKey(complement)) {return new int[] { numMap.get(complement), i };}numMap.put(nums[i], i);}return new int[0];}
}

關鍵點解析

特性	說明
時間復雜度O(n)	哈希表使查找時間降為O(1)，只需一次遍歷
空間復雜度O(n)	最壞情況需存儲所有元素
防重復機制	先檢查補數再存入當前元素，避免自重復（如target=6, nums=[3,3]場景）
鍵值設計	鍵為數組值，值為索引，便于快速查找

復雜度對比

方法	時間復雜度	空間復雜度	適用場景
暴力枚舉	O(n2)	O(1)	小規模數據
哈希表	O(n)	O(n)	通用最優解

---

3. 三數之和（3Sum）

3.1 問題描述

15. 三數之和

3.2 排序+雙指針解法

代碼實現

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class ThreeSum {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();if (nums == null || nums.length < 3) return result;Arrays.sort(nums); // 關鍵預處理for (int i = 0; i < nums.length - 2; i++) {if (i > 0 && nums[i] == nums[i-1]) continue; // 跳過重復起點if (nums[i] > 0) break; // 提前終止int left = i + 1, right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {result.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 (sum < 0) {left++; // 需要更大的數} else {right--; // 需要更小的數}}}return result;}
}

關鍵點解析

策略	作用
排序預處理	使雙指針法成為可能，同時便于去重
外層循環去重	if (i>0 && nums[i]==nums[i-1]) 避免重復的基準元素
雙指針收縮	當sum=0時同時移動左右指針，避免遺漏解
內層循環去重	在找到有效解后，跳過所有與當前左右指針相同的元素
提前終止條件	當基準元素nums[i]>0時，后續不可能出現有效解

復雜度分析

操作	時間復雜度	說明
排序	O(n log n)	快速排序基礎復雜度
雙指針遍歷	O(n2)	外層循環O(n)，內層雙指針O(n)
總復雜度	O(n2)	主導項為雙指針遍歷

---

4. 對比總結

維度	兩數之和	三數之和
核心思想	哈希表快速查找	排序+雙指針+去重
時間復雜度	O(n)	O(n2)
空間復雜度	O(n)	O(1)（不計結果存儲）
難點	避免元素自重復	多維度去重與指針協同移動
擴展性	可擴展至Two Sum II（有序數組）	可擴展至4Sum、KSum問題

---

5. 常見問題解答

Q1：為什么三數之和需要先排序？
排序后可以使用雙指針法將時間復雜度從O(n3)優化到O(n2)，同時便于跳過重復元素。

Q2：如何處理輸入數組中的重復元素？

• 外層循環跳過相同基準元素
• 找到有效解后，內層循環跳過相同左右指針值

Q3：哈希表法為什么不適合三數之和？
雖然理論上可以使用哈希表存儲兩數之和，但難以高效處理去重問題，且空間復雜度會顯著增加。

---

6. 擴展練習

1. 四數之和（4Sum）：嘗試將三數之和的解法擴展到四數之和
2. 最接近的三數之和：尋找與目標值最接近的三數組合
3. 兩數之和變種：設計支持頻繁查詢的數據結構

---

通過掌握這兩個經典問題的解法，可以深入理解哈希表與雙指針法的應用場景，并為解決更復雜的KSum問題打下堅實基礎。