Two Pointers Pattern: Đảo mảng, kiểm tra chuỗi đối xứng và tìm cặp số

Two Pointers Pattern: Đảo mảng, kiểm tra chuỗi đối xứng và tìm cặp số | Shanverse

Codetypescript

1let left = 0;2let right = items.length - 1;34while (left < right) {5  // Inspect items[left] and items[right].67  if (shouldMoveLeft()) left++;8  else if (shouldMoveRight()) right--;9  else {10    left++;11    right--;12  }13}

Codetypescript

1function reverseInPlace<T>(items: T[]): T[] {2  let left = 0;3  let right = items.length - 1;45  while (left < right) {6    [items[left], items[right]] = [items[right], items[left]];7    left++;8    right--;9  }1011  return items;12}

Codetypescript

1function isAsciiAlphaNumeric(character: string): boolean {2  const code = character.charCodeAt(0);3  return (4    (code >= 48 && code <= 57) ||5    (code >= 65 && code <= 90) ||6    (code >= 97 && code <= 122)7  );8}910function isPalindrome(text: string): boolean {11  let left = 0;12  let right = text.length - 1;1314  while (left < right) {15    while (left < right && !isAsciiAlphaNumeric(text[left])) {16      left++;17    }1819    while (left < right && !isAsciiAlphaNumeric(text[right])) {20      right--;21    }2223    if (text[left].toLowerCase() !== text[right].toLowerCase()) {24      return false;25    }2627    left++;28    right--;29  }3031  return true;32}

Codetypescript

1function twoSumSorted(2  numbers: readonly number[],3  target: number,4): [number, number] | null {5  let left = 0;6  let right = numbers.length - 1;78  while (left < right) {9    const sum = numbers[left] + numbers[right];1011    if (sum === target) return [left, right];12    if (sum < target) left++;13    else right--;14  }1516  return null;17}

Codetypescript

1function twoSumUnsorted(2  numbers: readonly number[],3  target: number,4): [number, number] | null {5  const seen = new Map<number, number>();67  for (let index = 0; index < numbers.length; index++) {8    const complement = target - numbers[index];9    const match = seen.get(complement);1011    if (match !== undefined) return [match, index];12    seen.set(numbers[index], index);13  }1415  return null;16}

Codetypescript

1function uniquePairsWithSum(2  sorted: readonly number[],3  target: number,4): Array<[number, number]> {5  const pairs: Array<[number, number]> = [];6  let left = 0;7  let right = sorted.length - 1;89  while (left < right) {10    const leftValue = sorted[left];11    const rightValue = sorted[right];12    const sum = leftValue + rightValue;1314    if (sum < target) {15      left++;16      continue;17    }1819    if (sum > target) {20      right--;21      continue;22    }2324    pairs.push([leftValue, rightValue]);2526    while (left < right && sorted[left] === leftValue) left++;27    while (left < right && sorted[right] === rightValue) right--;28  }2930  return pairs;31}

Codetypescript

1function removeDuplicates(sorted: number[]): number {2  if (sorted.length === 0) return 0;34  let write = 1;56  for (let read = 1; read < sorted.length; read++) {7    if (sorted[read] !== sorted[write - 1]) {8      sorted[write] = sorted[read];9      write++;10    }11  }1213  return write;14}

Codetypescript

1function moveZeroes(numbers: number[]): void {2  let write = 0;34  for (let read = 0; read < numbers.length; read++) {5    if (numbers[read] !== 0) {6      [numbers[write], numbers[read]] = [numbers[read], numbers[write]];7      write++;8    }9  }10}

Codetypescript

1type ListNode<T> = {2  value: T;3  next: ListNode<T> | null;4};56function hasCycle<T>(head: ListNode<T> | null): boolean {7  let slow = head;8  let fast = head;910  while (fast !== null && fast.next !== null) {11    slow = slow!.next;12    fast = fast.next.next;1314    if (slow === fast) return true;15  }1617  return false;18}

Codetypescript

1function threeSum(numbers: readonly number[]): number[][] {2  const sorted = [...numbers].sort((a, b) => a - b);3  const result: number[][] = [];45  for (let index = 0; index < sorted.length - 2; index++) {6    if (index > 0 && sorted[index] === sorted[index - 1]) continue;7    if (sorted[index] > 0) break;89    let left = index + 1;10    let right = sorted.length - 1;1112    while (left < right) {13      const sum = sorted[index] + sorted[left] + sorted[right];1415      if (sum < 0) {16        left++;17      } else if (sum > 0) {18        right--;19      } else {20        result.push([sorted[index], sorted[left], sorted[right]]);21        const leftValue = sorted[left];22        const rightValue = sorted[right];2324        while (left < right && sorted[left] === leftValue) left++;25        while (left < right && sorted[right] === rightValue) right--;26      }27    }28  }2930  return result;31}

Two Pointers Pattern: Đảo mảng, kiểm tra chuỗi đối xứng và tìm cặp số

Two Pointers là gì?

Comments

Các biến thể chính

Khi nào nên nghĩ đến Two Pointers?

Mẫu 1: Hai con trỏ từ hai đầu

Ví dụ 1: Đảo mảng in-place

Invariant

Ví dụ 2: Kiểm tra chuỗi đối xứng

Unicode không đơn giản

Ví dụ 3: Tìm cặp số trong mảng đã sort

Vì sao di chuyển đúng?

Mảng chưa sort

Trả về mọi pair duy nhất

Mẫu 2: Read/Write Pointers

Xóa duplicate khỏi sorted array

Invariant

Di chuyển số 0 về cuối

Mẫu 3: Fast/Slow Pointers

Mở rộng thành 3Sum

Two Pointers và Sliding Window khác nhau thế nào?

Chứng minh độ phức tạp

Lỗi thường gặp

1. Quên precondition sorted

2. Sort làm mất index hoặc mutate input

3. Infinite loop

4. Dùng left <= right sai chỗ

5. Xử lý duplicate không đúng yêu cầu

6. So sánh số thực bằng ===

7. Unicode/case normalization mơ hồ

8. Tuyên bố O(1) nhưng đã tạo copy

Edge cases cần test

Quy trình giải bài Two Pointers

Kết luận

Fast & Slow Pointers: Phát hiện vòng lặp bằng thuật toán Floyd

Monotonic Stack & Queue: Tìm phần tử lớn hơn hoặc nhỏ hơn tiếp theo trong O(N)

Trie (Prefix Tree): Xây dựng Search Suggestion và Autocomplete siêu tốc

Two Pointers là gì?

Comments

Các biến thể chính

Khi nào nên nghĩ đến Two Pointers?

Mẫu 1: Hai con trỏ từ hai đầu

Ví dụ 1: Đảo mảng in-place

Invariant

Ví dụ 2: Kiểm tra chuỗi đối xứng

Unicode không đơn giản

Ví dụ 3: Tìm cặp số trong mảng đã sort

Vì sao di chuyển đúng?

Mảng chưa sort

Trả về mọi pair duy nhất

Mẫu 2: Read/Write Pointers

Xóa duplicate khỏi sorted array

Invariant

Di chuyển số 0 về cuối

Mẫu 3: Fast/Slow Pointers

Mở rộng thành 3Sum

Two Pointers và Sliding Window khác nhau thế nào?

Chứng minh độ phức tạp

Lỗi thường gặp

1. Quên precondition sorted

2. Sort làm mất index hoặc mutate input

3. Infinite loop

4. Dùng left <= right sai chỗ

5. Xử lý duplicate không đúng yêu cầu

6. So sánh số thực bằng ===

7. Unicode/case normalization mơ hồ

8. Tuyên bố O(1) nhưng đã tạo copy

Edge cases cần test

Quy trình giải bài Two Pointers

Kết luận

Related posts

Fast & Slow Pointers: Phát hiện vòng lặp bằng thuật toán Floyd

Monotonic Stack & Queue: Tìm phần tử lớn hơn hoặc nhỏ hơn tiếp theo trong O(N)

Trie (Prefix Tree): Xây dựng Search Suggestion và Autocomplete siêu tốc