刷題最怕「背解法、不懂為什麼」。這篇不直接丟答案，而是帶你走完每題的完整推導流程：
拆解題目 → 寫出暴力解 → 找出瓶頸 → 抓到關鍵洞察 → 推導出最優解 → 程式碼
這 6 題（LC 1、167、15、11、3、76）剛好串成一條解法演進線——從雜湊、到雙指針、再到滑動視窗。看懂推導，面試遇到變體也能自己推出來。
三個核心模式
- HashMap（雜湊）：用空間換時間，把「找另一個數」從 O(n) 降到 O(1)。
- Two Pointers（雙指針）：前提是排序，靠左右指針的單調移動收斂答案。
- Sliding Window（滑動視窗）：右指針擴張、左指針收縮，維護一段「合法區間」。
💡 三者的關係：雜湊解決「無序找配對」；一旦排序，雙指針就能省掉雜湊的空間；當問題變成「連續區間」，雙指針就進化成滑動視窗。
① LC 1 — Two Sum
📋 題目：給定一個整數陣列 nums 與目標值 target，回傳兩個數的索引，使它們相加等於 target。可假設恰有一組解，且同一元素不能用兩次。
範例：nums = [2,7,11,15]、target = 9 → [0,1]（因為 nums[0] + nums[1] = 2 + 7 = 9）
🧭 從讀題到解法
- 拆解：輸入是無序陣列 + target，輸出是兩個索引。
- 暴力解：雙層迴圈，對每個
i往後找有沒有j讓nums[i]+nums[j]==target。時間 O(n²)。 - 瓶頸在哪：內層迴圈每次都在做同一件事——「線性搜尋我需要的另一半
target - nums[i]」。這個搜尋是 O(n)。 - 關鍵洞察：如果能用 O(1) 查「我需要的另一半之前有沒有出現過」，內層迴圈就消失了 → 用一個 HashMap 記錄「看過的值 → 它的索引」。
- 推導最優解：一邊遍歷，一邊問「
target - 當前數在表裡嗎？」在 → 回傳兩個索引；不在 → 把當前數存進表，繼續。
def twoSum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
if target - n in seen: # check before insert
return [seen[target - n], i]
seen[n] = i
return []
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen; // value -> index
for (int i = 0; i < (int)nums.size(); ++i) {
auto it = seen.find(target - nums[i]);
if (it != seen.end()) return {it->second, i};
seen[nums[i]] = i;
}
return {};
}
- 複雜度：時間 O(n)，空間 O(n)。
- 坑：一定要先查再放，否則會把自己當成配對。
② LC 167 — Two Sum II
📋 題目：給定一個已遞增排序的陣列 numbers 與目標值 target，找出兩個數相加等於 target，回傳它們的 1-indexed 索引 [index1, index2]。恰有一組解。
範例：numbers = [2,7,11,15]、target = 9 → [1,2]（2 + 7 = 9，索引從 1 開始算）
🧭 從讀題到解法
- 拆解：跟 LC1 幾乎一樣，但多了一個關鍵條件——已排序。
- 先想 LC1 解法：HashMap 一樣能解，O(n) 時間、O(n) 空間。但「已排序」這個條件完全沒用到——面試題給你的條件通常都是提示。
- 關鍵洞察：排序後，從最小（最左）+ 最大（最右） 開始看它們的和：
- 和太大 → 想變小，只能把右指針左移（換成更小的數）。
- 和太小 → 想變大，只能把左指針右移。
- 每一步都安全地排除掉一個元素，指針單調靠近。
- 推導最優解：左右指針相向移動，依
sum與target的比較決定誰動。空間降到 O(1)。
def twoSum(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed
elif s < target:
lo += 1 # need a bigger sum
else:
hi -= 1 # need a smaller sum
return []
vector<int> twoSum(vector<int>& numbers, int target) {
int lo = 0, hi = (int)numbers.size() - 1;
while (lo < hi) {
int s = numbers[lo] + numbers[hi];
if (s == target) return {lo + 1, hi + 1};
else if (s < target) ++lo;
else --hi;
}
return {};
}
- 複雜度：時間 O(n)，空間 O(1)。
- 坑：回傳是 1-indexed；雙指針成立的前提，就是「排序後移動方向是單調的」。
🔑 面試對比點：LC1 vs LC167 —— 「為什麼一個用 HashMap、一個用雙指針？」答：差在是否已排序。
③ LC 15 — 3Sum
📋 題目：給定整數陣列 nums，找出所有和為 0 的三元組 [nums[i], nums[j], nums[k]]（i、j、k 互不相同），結果不可包含重複的三元組。
範例：nums = [-1,0,1,2,-1,-4] → [[-1,-1,2], [-1,0,1]]
🧭 從讀題到解法
- 拆解：三個數和為 0，且結果不能有重複三元組。
- 從 2Sum 出發：三數和為 0 ⟺ 固定一個數
a，剩下兩個數要湊成-a——這不就是 Two Sum 嗎？ - 關鍵洞察：既然剩下要解 Two Sum，而 LC167 告訴我們「排序後用雙指針最省」，那就先排序，再固定
nums[i]，在它右邊用左右指針找-nums[i]。 - 處理去重（這題真正的難點）：排序後重複值會相鄰，所以——
- 固定數
nums[i]若和前一個相同就跳過（否則同樣的三元組會再算一次）。 - 找到一組解後，左右指針也要跳過相鄰的重複值。
- 固定數
- 剪枝：排序後若
nums[i] > 0，後面不可能再湊到 0，直接結束。
def threeSum(nums):
nums.sort()
res, n = [], len(nums)
for i in range(n - 2):
if nums[i] > 0: # smallest already > 0
break
if i > 0 and nums[i] == nums[i - 1]: # skip duplicate anchor
continue
lo, hi = i + 1, n - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0:
lo += 1
elif s > 0:
hi -= 1
else:
res.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]: # skip dups
lo += 1
while lo < hi and nums[hi] == nums[hi + 1]:
hi -= 1
return res
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < n - 2; ++i) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip anchor dup
int lo = i + 1, hi = n - 1;
while (lo < hi) {
int s = nums[i] + nums[lo] + nums[hi];
if (s < 0) ++lo;
else if (s > 0) --hi;
else {
res.push_back({nums[i], nums[lo], nums[hi]});
++lo; --hi;
while (lo < hi && nums[lo] == nums[lo - 1]) ++lo;
while (lo < hi && nums[hi] == nums[hi + 1]) --hi;
}
}
}
return res;
}
- 複雜度：時間 O(n²)，空間 O(1)（不算排序與輸出）。
- 坑：三層去重——固定數
i要跳重複、找到解後lo/hi也要跳重複。漏任何一層都會出現重複三元組。
④ LC 11 — Container With Most Water
📋 題目：給定 n 個非負整數 height，每個代表座標上一條垂直線的高度。選兩條線，與 x 軸圍成一個容器，回傳能裝的最大水量。水量 = min(height[i], height[j]) × (j - i)。
範例：height = [1,8,6,2,5,4,8,3,7] → 49（選高度 8 與 7，寬 7，面積 7 × 7 = 49）
🧭 從讀題到解法
- 拆解：面積 =
min(左高, 右高) × 兩線間距，要最大化。 - 暴力解：列舉所有 pair 算面積取最大，O(n²)。
- 關鍵洞察（貪心）：先從最寬開始——左右兩端，寬度最大。此時若想讓面積更大，唯一變數是「高」。問題是該移哪一邊？
- 面積被較矮那條線限制。若移動較高那邊：寬一定變小、高仍卡在原本那條矮線 → 面積不可能變大。
- 只有移動較矮那邊，才有機會換到更高的線、讓面積變大。
- 推導最優解：左右指針從兩端開始，每次移動較矮的一邊，沿路記錄最大面積。每個元素只看一次 → O(n)。
def maxArea(height):
lo, hi, best = 0, len(height) - 1, 0
while lo < hi:
h = min(height[lo], height[hi])
best = max(best, h * (hi - lo))
if height[lo] < height[hi]: # move the shorter side
lo += 1
else:
hi -= 1
return best
int maxArea(vector<int>& height) {
int lo = 0, hi = (int)height.size() - 1, best = 0;
while (lo < hi) {
int h = min(height[lo], height[hi]);
best = max(best, h * (hi - lo));
if (height[lo] < height[hi]) ++lo;
else --hi;
}
return best;
}
- 複雜度：時間 O(n)，空間 O(1)。
- 坑（最常被追問）：上面第 3 點「為什麼移較矮那邊」就是貪心的正確性證明，面試一定要講得出來。
🔑 面試對比點：LC11 vs LC167 —— 同樣是左右雙指針，但 167 靠「和與 target 比較」決定方向，11 靠「哪邊比較矮」決定方向。
⑤ LC 3 — Longest Substring Without Repeating Characters
📋 題目：給定字串 s，找出其中不含重複字元的最長子字串長度。
範例：s = "abcabcbb" → 3（最長為 "abc"）；s = "pwwkew" → 3（"wke"）
🧭 從讀題到解法
- 拆解：關鍵字「子字串」=連續區間（不是子序列）；要「最長」且「無重複」。
- 暴力解：列舉所有起點、終點，逐一檢查是否無重複，O(n²) 甚至 O(n³)。
- 關鍵洞察：維護一個視窗
[left, right]代表「目前這段無重複」。右指針一直往右擴；一旦遇到已在視窗內的重複字元，就把left跳到「那個重複字元上次出現位置 + 1」，讓視窗重新合法。 - 推導最優解：用一個 map 記「每個字元最後出現的位置」。右指針前進時，若當前字元上次出現位置
>= left（代表在視窗內），就把left推進。每步更新最長長度。左右指針各只前進 → O(n)。
def lengthOfLongestSubstring(s):
last = {} # char -> last index seen
left = best = 0
for right, c in enumerate(s):
if c in last and last[c] >= left:
left = last[c] + 1 # jump past the duplicate
last[c] = right
best = max(best, right - left + 1)
return best
int lengthOfLongestSubstring(string s) {
vector<int> last(128, -1); // char -> last index
int left = 0, best = 0;
for (int right = 0; right < (int)s.size(); ++right) {
if (last[s[right]] >= left)
left = last[s[right]] + 1;
last[s[right]] = right;
best = max(best, right - left + 1);
}
return best;
}
- 複雜度：時間 O(n)，空間 O(min(n, 字元集))。
- 坑：判斷必須是
last[c] >= left。如果重複字元落在視窗外（在left左邊），就不該縮窗——少了這個條件是最常見的 bug。
⑥ LC 76 — Minimum Window Substring
📋 題目：給定字串 s 與 t，回傳 s 中最短的子字串，使其包含 t 的所有字元（含重複次數）。若不存在則回傳空字串 ""。
範例：s = "ADOBECODEBANC"、t = "ABC" → "BANC"
🧭 從讀題到解法
- 拆解：一樣是「連續子字串」，但這次求最短，而且條件升級成「要涵蓋
t的一整組字元需求（含次數）」。 - 從 LC3 出發：LC3 是變長視窗求最長；這題也是變長視窗，但求最短、判斷條件更複雜。框架一樣：右擴、左縮。
- 關鍵洞察（擴張 vs 收縮的時機）：
- 右指針一直擴張，直到視窗涵蓋了
t。 - 一旦涵蓋，就盡量把左指針往右縮，縮到「再縮一格就不涵蓋」為止——這個過程中記錄最短長度。
- 然後右指針繼續擴張，重複。
- 右指針一直擴張，直到視窗涵蓋了
- 怎麼 O(1) 判斷「是否涵蓋」：用
need[字元]計數（還差幾個某字元，可以變負代表多餘）+ 一個整數missing（總共還差幾個字元）。missing == 0就代表涵蓋了，不用每步比對整張表。 - 推導最優解：
- 擴張：
need[c] -= 1；若這個c是「需要的」（補進去前need[c] > 0），missing -= 1。 - 當
missing == 0：進入收縮迴圈，記錄最短；左縮時need[left] += 1，若縮掉的是「需要的」字元（need[left] > 0），missing += 1。
- 擴張：
from collections import Counter
def minWindow(s, t):
if not s or not t:
return ""
need = Counter(t)
missing = len(t) # how many chars still needed
left = 0
best = (float('inf'), 0, 0) # (length, start, end)
for right, c in enumerate(s):
if need[c] > 0:
missing -= 1
need[c] -= 1 # may go negative (surplus)
while missing == 0: # window covers t -> try to shrink
if right - left + 1 < best[0]:
best = (right - left + 1, left, right + 1)
need[s[left]] += 1
if need[s[left]] > 0: # we just dropped a needed char
missing += 1
left += 1
return "" if best[0] == float('inf') else s[best[1]:best[2]]
string minWindow(string s, string t) {
if (s.empty() || t.empty()) return "";
vector<int> need(128, 0);
for (char c : t) need[c]++;
int missing = t.size(), left = 0;
int bestLen = INT_MAX, bestStart = 0;
for (int right = 0; right < (int)s.size(); ++right) {
if (need[s[right]] > 0) --missing;
need[s[right]]--; // may go negative
while (missing == 0) { // covers t -> shrink
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
need[s[left]]++;
if (need[s[left]] > 0) ++missing; // dropped a needed char
++left;
}
}
return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}
- 複雜度：時間 O(|s| + |t|)，空間 O(字元集)。
- 坑：
need計數可以變負（代表視窗內某字元超量）；用一個missing整數計數，比每次比對整張 map 快得多；只有missing == 0時才縮左指針。
🔑 面試對比點：LC3 vs LC76 —— 都是變長滑窗，但 LC3 求最長（擴張時更新答案），LC76 求最短（收縮時更新答案）。
一張表記住全部
| 題 | 推導起點 | 模式 | 時間 | 關鍵招式 / 坑 |
|---|---|---|---|---|
| LC 1 | 暴力 → 消掉內層搜尋 | HashMap | O(n) | 先查再放 |
| LC 167 | 利用「已排序」條件 | 雙指針 | O(n) | 1-indexed；方向單調 |
| LC 15 | 固定一數 → 退化成 2Sum | 雙指針 | O(n²) | 三層去重 |
| LC 11 | 從最寬開始 + 貪心 | 貪心雙指針 | O(n) | 移較矮邊（要會證明） |
| LC 3 | 維護無重複視窗 | 滑窗（最長） | O(n) | last[c] >= left |
| LC 76 | 從 LC3 升級判斷條件 | 滑窗（最短） | O( | s |
面試辨識口訣
- 看到「兩數湊定值」→ 未排序用 HashMap，已排序用雙指針。
- 看到「多數湊定值 + 去重」→ 排序 + 固定數 + 雙指針。
- 看到「左右兩端最大化」→ 貪心雙指針，移較矮邊。
- 看到「連續子字串/子陣列 + 最長或最短」→ 滑動視窗；最長在擴張時記錄、最短在收縮時記錄。
推導流程比死背更重要：面試時把「暴力 → 瓶頸 → 洞察 → 最優」講出來，就算卡住，面試官也看得到你的思路。