Problem: 1. 兩數之和

整體思路

這段代碼旨在高效地解決 “兩數之和” 問題。與 O(N^2) 的暴力枚舉法相比，此版本采用了一種經典的 “空間換時間” 策略，利用 哈希表 (HashMap) 將時間復雜度優化到了線性級別 O(N)。

該算法的核心思想是，在遍歷數組的同時，利用哈希表快速查找每個數字所需的“另一半”。

算法的邏輯步驟可以分解如下：

1. 數據結構選擇：

   • 算法選擇 HashMap 作為核心數據結構。這個哈希表將用于存儲已經遍歷過的數字及其對應的索引，即 (數字 -> 索引) 的鍵值對。
   • 目的：哈希表提供了平均時間復雜度為 O(1) 的查找操作。這使得我們能夠即時地回答“我們之前是否見過某個數字？”這個問題。

2. 單次遍歷與查找：

   • 算法只需對 nums 數組進行一次 for 循環遍歷。
   • 在循環的每一步（對于當前數字 nums[i]），算法執行兩個核心操作，且順序非常關鍵：
     a. 計算并查找“補數”：首先，計算出要與 nums[i] 相加才能得到 target 的那個“補數” other，即 other = target - nums[i]。然后，算法立即在哈希表中檢查是否存在這個 other。
     b. 處理查找結果：
     • 如果找到了 (map.containsKey(other))：這意味著 other 這個數字在數組的前面部分（0 到 i-1 的索引中）已經出現過。我們已經找到了解！此時，直接返回 other 的索引（從哈希表中獲取 map.get(other)）和當前數字的索引 i。
     • 如果沒有找到：這意味著在已經遍歷過的數字中，沒有 nums[i] 的“另一半”。那么，nums[i] 本身可能就是未來某個數字的“另一半”。因此，算法將當前數字 nums[i] 及其索引 i 存入哈希表中，以供后續的迭代查找。

3. 返回結果：

   • 由于題目保證有且僅有一個解，if 條件一定會在某個時刻被滿足并返回結果。因此，理論上最后的 return null; 是不可達的（但在語法上是必需的，以防編譯器報錯）。

通過這種“邊遍歷邊記錄”的方式，算法將尋找配對數的過程從 O(N) 的線性掃描縮短為 O(1) 的哈希查找，從而實現了整體性能的飛躍。

完整代碼

import java.util.HashMap;
import java.util.Map;class Solution {/*** 在數組中找出和為目標值的兩個數的索引。* @param nums 整數數組* @param target 目標和* @return 包含兩個索引的數組，如果不存在則返回 null*/public int[] twoSum(int[] nums, int target) {int n = nums.length;// map: 用于存儲已遍歷過的數字及其索引。// Key: 數組中的數字// Value: 該數字對應的索引Map<Integer, Integer> map = new HashMap<>();// 單次遍歷數組for (int i = 0; i < n; i++) {// 計算當前數字 nums[i] 需要配對的“另一半”int other = target - nums[i];// 關鍵步驟：檢查“另一半”是否已經存在于哈希表中// 這是 O(1) 的高效查找操作if (map.containsKey(other)) {// 如果存在，說明我們找到了解。// map.get(other) 是“另一半”的索引，i 是當前數字的索引。return new int[]{map.get(other), i};}// 如果“另一半”不存在，則將當前數字和它的索引存入哈希表，// 以便后續的元素可以查找它作為配對。map.put(nums[i], i);}// 根據題目假設，總會有一個解，所以理論上不會執行到這里。return null;}
}

時空復雜度

時間復雜度：O(N)

1. 循環：算法的核心是一個 for 循環，它嚴格地遍歷 nums 數組一次。如果數組的長度為 N，這個循環將執行 N 次。
2. 循環內部操作：
   • 在循環的每一次迭代中，執行的主要操作是 map.containsKey() 和 map.put()。
   • 對于 HashMap，這兩個操作的平均時間復雜度都是 O(1)。
   • 其余的算術和賦值操作也是 O(1)。

綜合分析：
算法由 N 次 O(1) 的操作組成。因此，總的時間復雜度是 N * O(1) = O(N)。

空間復雜度：O(N)

1. 主要存儲開銷：算法使用了一個哈希表 map 來存儲已經遍歷過的數字和它們的索引。
2. 空間大小：在最壞的情況下（例如，解在數組的最后兩個元素，或者無解），哈希表需要存儲 N-1 或 N 個鍵值對。因此，哈希表占用的空間與輸入數組 nums 的大小 N 成線性關系。

綜合分析：
算法所需的額外空間主要由哈希表 map 決定。因此，其空間復雜度為 O(N)。