Pattern — Two Sum Variants

Khi nào dùng

Bài hỏi “tìm 2 phần tử / cặp / k phần tử có tổng (hiệu, tích) = target” trong array.

Decision tree

Có sorted không?
├─ YES → Two Pointers — O(N), O(1) space
└─ NO  → HashMap — O(N), O(N) space  (mặc định)

Nếu được phép sort & cần $O(1)$ extra space → sort + two pointers, $O(N\log N)$.

Variants

Bài	LC	Pattern chính
Two Sum	LC-1	HashMap
Two Sum II — sorted	LC #167	Two Pointers
3Sum	LC #15	Sort + 3-pointers + skip duplicates
3Sum Closest	LC #16	Sort + 3-pointers + min
4Sum	LC #18	Sort + 4-pointers (or 2-pointer + 2 outer loops)
Two Sum III (data structure)	LC #170	HashMap với multi-set của freq
Two Sum IV (BST)	LC #653	BST inorder + two pointers
Subarray Sum = K	LC #560	Prefix sum + HashMap — rất khác!
Continuous Subarray Sum	LC #523	Prefix sum mod K

Pitfalls

1. Skip duplicates trong 3Sum: while (i < N-1 && nums[i]==nums[i+1]) i++ — SAU khi đã ghi nhận đáp án hợp lệ.
2. HashMap collision: cần check if (map.has(complement) && map.get(complement) !== i) để không trùng index.
3. 3Sum không sort: phải dùng Set đúng cách hoặc sẽ duplicate triplets.
4. Overflow: $a+b$ có thể overflow với int32 — Python/JS không vấn đề, Java/C++ cần long.

Top 5 problems (priority)

1. LC #1 — Two Sum (HashMap)
2. LC #167 — Two Sum II Sorted (Two Pointers)
3. LC #15 — 3Sum (Sort + skip dup)
4. LC #560 — Subarray Sum K (Prefix + HashMap)
5. LC #18 — 4Sum (Generalize)

→ Nguồn lý thuyết: 07-Hash-Table, 01-Two-Pointers-Sliding-Window