Khi nào dùng Two Pointers thay vì Hash Map cho bài tìm cặp?

Two Pointers ưu thế khi mảng đã được sắp xếp — không cần extra space, đạt O(n) time, O(1) space.

Hash Map cần O(n) space để đổi lấy O(1) lookup. Trên mảng sorted, Two Pointers đạt cùng O(n) time mà không cần buffer.

Phân biệt:
- Mảng sorted + tìm cặp tổng = target → Two Pointers
- Mảng KHÔNG sorted + cần O(n) → Hash Map
- Cần O(1) space và mảng sorted → Two Pointers
- Cần đếm tần suất → Hash Map (Two Pointers không phù hợp)

Code (Two Sum Sorted):

function twoSumSorted(nums: number[], target: number) {
  let left = 0, right = nums.length - 1
  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) return [left, right]
    if (sum < target) left++
    else right--
  }
  return null
}