Two Sum II: tại sao thứ tự đã sắp xếp làm two pointers hoạt động

Two Sum gốc cho bạn một mảng chưa sắp xếp và cho phép dùng hash map. Bài này lấy đi sự tiện lợi đó và thay thế bằng thứ có giá trị hơn: một đảm bảo. Mảng đã được sắp xếp. Một thực tế đơn giản đó thay đổi toàn bộ cấu trúc của solution.

Bài toán thực sự cho bạn gì

numbers là 1-indexed, sắp xếp theo thứ tự không giảm, và chính xác một cặp chỉ số có tổng bằng target. Constraints: tối đa 30.000 phần tử, giá trị và target đều trong khoảng [-1000, 1000], và — quan trọng nhất — bạn phải dùng constant extra space. Ràng buộc cuối đó loại bỏ cách tiếp cận hash map ngay từ đầu.

Hai ràng buộc cùng nhau chỉ bạn đến một câu trả lời. Câu hỏi không phải là "làm thế nào để tìm một cặp?" Mà là "làm thế nào để khai thác thứ tự đã sắp xếp để tìm cặp trong linear time?"

Brute force: O(n²)

Cách naive là hai vòng lặp lồng nhau — thử mọi cặp, trả về khi tổng khớp.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        n = len(numbers)
        for i in range(n - 1):
            for j in range(i + 1, n):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]
        return []

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int n = numbers.Length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (numbers[i] + numbers[j] == target)
                    return new int[] { i + 1, j + 1 };
            }
        }
        return new int[0];
    }
}

O(n²) time, O(1) space. Thỏa mãn ràng buộc về space nhưng bỏ qua hoàn toàn tính chất sorted. Với mảng 30.000 phần tử, bạn đang nhìn vào tới 450 triệu phép so sánh. Nó sẽ pass judge của LeetCode vì constraints đủ nhỏ — nhưng đó là bài học sai. Mục tiêu của bài này không phải sống sót qua nó, mà là hiểu tại sao việc sắp xếp mở ra điều gì đó tốt hơn.

Đi qua ví dụ 1: numbers = [2, 7, 11, 15], target = 9.

• i=0, j=1: 2 + 7 = 9. Khớp. Return [1, 2].

Xong ngay cặp đầu tiên. Trong worst case, cặp đáp án nằm gần cuối và bạn phải duyệt gần như toàn bộ các tổ hợp trước khi tìm được.

Binary search: O(n log n)

Việc sắp xếp cho phép bạn làm điều thông minh hơn. Cố định phần tử bên trái, binary search để tìm complement target - numbers[i] trong suffix còn lại.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        def binary_search(start: int, val: int) -> int:
            lo, hi = start, len(numbers) - 1
            while lo <= hi:
                mid = (lo + hi) // 2
                if numbers[mid] == val:
                    return mid
                elif numbers[mid] < val:
                    lo = mid + 1
                else:
                    hi = mid - 1
            return -1
 
        for i in range(len(numbers) - 1):
            complement = target - numbers[i]
            j = binary_search(i + 1, complement)
            if j != -1:
                return [i + 1, j + 1]
        return []

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int BinarySearch(int start, int val) {
            int lo = start, hi = numbers.Length - 1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (numbers[mid] == val) return mid;
                else if (numbers[mid] < val) lo = mid + 1;
                else hi = mid - 1;
            }
            return -1;
        }
 
        for (int i = 0; i < numbers.Length - 1; i++) {
            int complement = target - numbers[i];
            int j = BinarySearch(i + 1, complement);
            if (j != -1)
                return new int[] { i + 1, j + 1 };
        }
        return new int[0];
    }
}

Đi qua ví dụ 2: numbers = [2, 3, 4], target = 6.

• i=0: complement = 6 - 2 = 4. Binary search trong [3, 4] từ index 1. mid=1, 3 < 4, move lo lên 2. mid=2, 4 == 4. Tìm thấy tại index 2. Return [1, 3].

O(n log n) time, O(1) space. Tốt hơn brute force. Nhưng có sự lãng phí mang tính cấu trúc: binary search cho i=0 khám phá nhiều phần của nửa phải. Search cho i=1 bỏ qua tất cả và bắt đầu lại. Bạn đang trả tiền cho kiến thức mà bạn ngay lập tức vứt đi.

Two pointers: O(n)

Đặt một pointer ở index 0 (left), một pointer ở index n-1 (right). Tính numbers[left] + numbers[right]. Nếu bằng target, trả về ngay. Nếu tổng nhỏ hơn target, bạn cần giá trị lớn hơn — right đã ở mức trần trong window hiện tại, vậy di chuyển left sang phải. Nếu tổng vượt target, bạn cần giá trị nhỏ hơn — left đang ở mức sàn, vậy kéo right sang trái.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            current = numbers[left] + numbers[right]
            if current == target:
                return [left + 1, right + 1]
            elif current < target:
                left += 1
            else:
                right -= 1
        return []

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int left = 0, right = numbers.Length - 1;
        while (left < right) {
            int current = numbers[left] + numbers[right];
            if (current == target)
                return new int[] { left + 1, right + 1 };
            else if (current < target)
                left++;
            else
                right--;
        }
        return new int[0];
    }
}

Đi qua ví dụ 1: numbers = [2, 7, 11, 15], target = 9.

left=0, right=3: 2 + 15 = 17 > 9  -> di chuyển right sang trái
left=0, right=2: 2 + 11 = 13 > 9  -> di chuyển right sang trái
left=0, right=1: 2 +  7 =  9 == 9 -> return [1, 2]

Đi qua ví dụ 3: numbers = [-1, 0], target = -1.

left=0, right=1: -1 + 0 = -1 == -1 -> return [1, 2]

Two pointers kết thúc ngay lập tức khi mảng chỉ có hai phần tử — đây là kích thước tối thiểu mà constraints cho phép.

Quá trình hội tụ của pointer trên ví dụ 1, từng bước:

O(n) time, O(1) space. Mỗi bước di chuyển ít nhất một pointer. Các pointer hội tụ. Mỗi phần tử được thăm tối đa một lần.

Tại sao mỗi bước di chuyển là an toàn, không chỉ là nhanh

Lập luận về tính đúng đắn đáng để hiểu kỹ, vì đây là lập luận làm cho two pointers hoạt động trên nhiều bài khác.

Logic quyết định tại mỗi bước:

Tại bất kỳ điểm nào trong vòng lặp, đáp án phải có left_answer >= left và right_answer <= right. Các pointer luôn bao quanh solution.

Khi chúng ta di chuyển left vì tổng quá nhỏ: chúng ta không chỉ di chuyển một pointer, chúng ta đang loại bỏ mọi cặp (left, j) cho tất cả j trong [left+1, right] cùng một lúc. Tại sao? Vì numbers[left] + numbers[j] <= numbers[left] + numbers[right] < target cho mọi j đó. numbers[left] hiện tại không thể ghép với bất cứ thứ gì trong window còn lại để đạt target. Loại bỏ nó không mất gì.

Khi chúng ta di chuyển right vì tổng quá lớn: numbers[i] + numbers[right] >= numbers[left] + numbers[right] > target cho mọi i trong [left, right-1]. numbers[right] hiện tại quá lớn cho bất kỳ đối tác còn lại nào. Loại bỏ nó là an toàn.

Đây không phải đoán mò. Mỗi lần di chuyển là một bằng chứng bằng cách loại trừ — và loại trừ chỉ an toàn vì mảng đã được sắp xếp. Bỏ đảm bảo sorted đó đi, và cả hai bước loại trừ đều bị phá vỡ. Đó chính xác là lý do tại sao bạn không thể áp dụng cùng thủ thuật cho Two Sum gốc mà không sort nó trước (và nếu sort, bạn cần theo dõi các index gốc riêng biệt).

So sánh các approaches

Cách tiếp cận binary search có chỗ đứng của nó: trong các bài toán mà bạn cần search trong một prefix hoặc suffix cố định, hoặc khi lập luận loại trừ của two pointers không áp dụng được. Nhưng với cấu trúc cụ thể này — tìm một cặp, mảng sorted, constant space — two pointers là câu trả lời chuẩn.

Edge cases đáng biết

Mảng hai phần tử. Chỉ với hai phần tử, left=0 và right=1 ngay ở iteration đầu. Bài đảm bảo có đúng một solution, vậy return ngay lập tức. Không cần xử lý đặc biệt.

Số âm. Constraints cho phép giá trị xuống đến -1000 và target xuống đến -1000. Two pointers xử lý tự nhiên — logic di chuyển chỉ phụ thuộc vào việc tổng hiện tại lớn hơn hay nhỏ hơn target, không phụ thuộc vào dấu.

Đáp án ở hai đầu mảng. Nếu numbers[0] + numbers[n-1] == target, đáp án tìm được ngay ở iteration đầu tiên. Nếu đáp án ở giữa, các pointer sẽ hội tụ đến đó. Lập luận đúng đắn vẫn đúng trong cả hai trường hợp.

Giá trị trùng nhau. Bài không nói giá trị là duy nhất, chỉ nói có đúng một cặp chỉ số hợp lệ. Two pointers xử lý trùng lặp mà không cần sửa đổi — nếu numbers[left] bằng numbers[left+1], di chuyển left sẽ bỏ qua đến bản sao và thuật toán tiếp tục bình thường.

Nhận diện pattern này

Một vài từ khóa nên ngay lập tức gợi lên two pointers:

• "sorted array" + "find a pair" + bất kỳ điều kiện tổng/hiệu nào
• "constant extra space" (loại bỏ hash map)
• "1-indexed return" (chỉ là cosmetic — cộng 1 vào mỗi pointer trước khi return)
• Bất kỳ bài nào mà brute force là O(n²) và bạn được yêu cầu cải thiện, với input đã sorted

Pattern rộng hơn: bất cứ khi nào bạn có thể phát biểu "tổng hiện tại quá lớn -> thu nhỏ một phía; quá nhỏ -> mở rộng phía kia" với dữ liệu sorted, two pointers giảm O(n²) xuống O(n).

Điều constraint nói với bạn

Bài nói "solution của bạn phải chỉ dùng constant extra space." Đọc điều đó như: không hash map. Hash map sẽ cho bạn O(n) time nhưng O(n) space. Two pointers cho bạn O(n) time và O(1) space. Constraint không phải là hình phạt — đó là gợi ý rằng thứ tự sorted đang làm công việc nặng và bạn nên dùng nó trực tiếp.

Trong interview, tôi sẽ viết phiên bản two-pointer và giải thích lập luận về tính đúng đắn mà không cần được hỏi. Không phải để thể hiện — mà để chứng minh sự khác biệt giữa dùng một technique và hiểu nó. "Di chuyển left khi tổng quá nhỏ" là một quy tắc. "Di chuyển left loại bỏ tất cả các cặp còn lại cho index này, vì thứ tự sorted đảm bảo chúng đều thấp hơn target" là một lý do. Interviewer nghe câu trả lời đầu tiên mọi lúc. Họ nhớ câu trả lời thứ hai.

Các bài liên quan

• LeetCode 1 — Two Sum: cùng họ, mảng chưa sắp xếp, hash map thay vì two pointers. Bắt đầu ở đây nếu bạn chưa làm.
• LeetCode 15 — 3Sum: mở rộng sang ba phần tử. Vòng lặp ngoài cố định một số và chạy two pointers trên phần còn lại. Sorted order vẫn là chìa khóa.
• LeetCode 18 — 4Sum: mở rộng thêm sang bốn phần tử. Cùng cấu trúc, thêm hai vòng lặp lồng nhau.
• LeetCode 11 — Container With Most Water: two pointers từ hai đầu, di chuyển thanh ngắn hơn vào trong. Cùng logic loại trừ, mục tiêu khác.
• LeetCode 125 — Valid Palindrome: two pointers đi về phía nhau, kiểm tra ký tự thay vì tổng. Quy tắc di chuyển khác; pattern hội tụ giống nhau.