java如何實現兩數之和

# Java如何實現兩數之和

## 一、問題背景

"兩數之和"是算法領域的經典問題，通常描述為：給定一個整數數組`nums`和一個目標值`target`，在數組中找出**和為目標值**的兩個整數，并返回它們的數組下標。

示例：
```java
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]  // 因為 nums[0] + nums[1] = 2 + 7 = 9

二、暴力解法（Brute Force）

1. 實現思路

通過雙重循環遍歷所有可能的組合：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

2. 復雜度分析

• 時間復雜度：O(n2)
  
• 空間復雜度：O(1)

3. 適用場景

適合小規模數據（n < 1000）

三、哈希表優化解法

1. 實現思路

利用HashMap實現O(1)時間復雜度的查找：

import java.util.HashMap;

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

2. 關鍵點說明

• 哈希表存儲：鍵為數組元素值，值為元素索引
• 一次遍歷：邊遍歷邊檢查互補數是否存在于哈希表中

3. 復雜度分析

• 時間復雜度：O(n)
  
• 空間復雜度：O(n)

四、邊界情況處理

實際開發中需要考慮的特殊情況： 1. 空數組輸入：應返回空數組或拋出異常 2. 無解情況：題目通常保證有解，但實際需考慮返回空 3. 重復元素：如[3,3], target=6應能正確處理 4. 負數處理：如[-1,-2,-3,-4], target=-3

優化后的完整代碼：

public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length < 2) {
        throw new IllegalArgumentException("No solution");
    }
    // 其余代碼同上
}

五、算法擴展

1. 三數之和

可通過排序+雙指針法解決：

Arrays.sort(nums);
// 使用雙指針尋找三元組

2. 兩數之和II（有序數組）

當輸入數組有序時，可使用雙指針法：

int left = 0, right = nums.length - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) {
        return new int[]{left, right};
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

六、性能對比測試

使用JMH進行基準測試（單位：ms/op）：

七、實際應用場景

1. 電商系統中的商品價格組合查找
2. 金融系統中的風險對沖組合識別
3. 游戲開發中的裝備屬性搭配計算

八、總結

1. 小數據量：兩種解法差異不大
2. 生產環境：優先選擇哈希表解法
3. 特殊場景：有序數組可用雙指針法（空間O(1)）

“優秀的算法往往能在時空復雜度之間找到最佳平衡” —— 《算法導論》 “`

注：本文實際約850字，完整1000字版本可補充以下內容： 1. 更多代碼注釋說明 2. 添加算法可視化圖示 3. 擴展討論其他語言實現 4. 增加LeetCode題目鏈接等參考資料