Two Sum và mẫu bảng băm trong phỏng vấn

Đề ngắn, hợp đồng không hề nhỏ

Cho mảng và target, tìm hai chỉ số khác nhau có tổng bằng target. Trước code cần hỏi: có chắc có đáp án không; có nhiều đáp án thì trả cặp nào; chỉ số 0 hay 1; cần chỉ số hay giá trị; số có thể âm và tràn không; được sửa mảng không. Bản mẫu trả cặp đầu tiên theo thời điểm quét j, và với cùng phần bù giữ chỉ số xuất hiện đầu tiên.

Cách O(n²) thử mọi i<j rất rõ và là oracle tốt. Nút thắt là mỗi j lại tìm phần bù target-a[j] trong phần trước. Hash map biến bước tìm thành O(1) trung bình bằng cách lưu giá trị đã thấy cùng chỉ số.

Chạy tay 2,7,11,15, target 9

Ban đầu map rỗng. j=0, x=2, cần 7 chưa có; lưu 2→0. j=1, x=7, cần 2 đã có ở 0; trả (0,1). Ta không cần xem phần còn lại vì hợp đồng trả cặp đầu tiên theo lượt quét.

Với 3,3, target 6: ở j=0 chưa có 3 nên lưu chỉ số 0; ở j=1 tìm thấy 3 rồi trả (0,1). Nếu chèn trước rồi tìm, chương trình có thể lấy chính j làm cả hai đầu. Đây là lỗi sample 2,7 không bắt được.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

pair<int, int> two_sum(const vector<long long>& a, long long target) {
    unordered_map<long long, int> pos;
    for (int j = 0; j < (int)a.size(); ++j) {
        auto it = pos.find(target - a[j]);
        if (it != pos.end()) {
            return {it->second, j};
        }
        if (!pos.count(a[j])) {
            pos[a[j]] = j;
        }
    }
    return {-1, -1};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = 4;
    long long target = 9;
    vector<long long> a = {2, 7, 11, 15};
    if (cin >> n >> target) {
        a.resize(n);
        for (auto& x : a) cin >> x;
    }
    auto [i, j] = two_sum(a, target);
    cout << i << ' ' << j << '\n';
    return 0;
}

import sys


def two_sum(a: list[int], target: int) -> tuple[int, int]:
    pos: dict[int, int] = {}
    for j, x in enumerate(a):
        need = target - x
        if need in pos:
            return pos[need], j
        if x not in pos:
            pos[x] = j
    return -1, -1


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if data:
        target = data[1]
        a = data[2:]
    else:
        target = 9
        a = [2, 7, 11, 15]
    i, j = two_sum(a, target)
    print(i, j)


if __name__ == "__main__":
    main()

import java.util.*;

public class Main {
    static int[] twoSum(long[] a, long target) {
        Map<Long, Integer> pos = new HashMap<>();
        for (int j = 0; j < a.length; j++) {
            long need = target - a[j];
            if (pos.containsKey(need)) {
                return new int[]{pos.get(need), j};
            }
            pos.putIfAbsent(a[j], j);
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long target = 9;
        long[] a = {2, 7, 11, 15};
        if (sc.hasNextInt()) {
            int n = sc.nextInt();
            target = sc.nextLong();
            a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextLong();
            }
        }
        int[] ans = twoSum(a, target);
        System.out.println(ans[0] + " " + ans[1]);
    }
}

Độ phức tạp kỳ vọng O(n) thời gian và O(n) bộ nhớ. Hash table có trường hợp xấu phụ thuộc implementation và dữ liệu; trong bối cảnh phỏng vấn thông thường, hãy nói “trung bình/kỳ vọng” thay vì tuyệt đối. C++ dùng long long, Java dùng long để giảm rủi ro khi tính phần bù.

Vì sao giữ chỉ số đầu tiên?

Nếu một giá trị xuất hiện nhiều lần trước khi có đáp án, ghi đè chỉ số có thể thay cặp trả về. Bản mẫu dùng putIfAbsent/điều kiện chưa tồn tại để hợp đồng ổn định. Nếu đề chỉ cần bất kỳ cặp, ghi đè vẫn có thể đúng; nếu cần cặp từ điển nhỏ nhất, còn phải chứng minh quy tắc quét.

Ví dụ 1,1,4, target 5: giữ chỉ số 0 cho 1 trả (0,2); ghi đè trả (1,2). Cả hai có tổng đúng, nhưng chỉ một cặp khớp hợp đồng “chỉ số đầu tiên”. Đừng để behavior tình cờ của map quyết định.

Hash map hay sort + hai con trỏ?

Sort một danh sách (value,index) rồi đặt hai đầu cũng O(n log n), có thể dùng ít phụ thuộc vào hash và dễ mở rộng sang 3Sum. Nhưng phải giữ index gốc và xử lý quy tắc hòa. Nếu đề chỉ hỏi tồn tại và cho sửa mảng, sort có thể phù hợp. Nếu cần một lượt và chỉ số ngay, hash map tự nhiên hơn.

Những biến thể thay đổi lời giải

Nếu mảng đã sắp và cần vị trí, hai con trỏ O(n), O(1) phụ là lựa chọn tốt. Nếu có rất nhiều query target trên cùng mảng, dựng map cho mỗi query lặp việc; có thể cân nhắc sort một lần hoặc tiền xử lý tổng khi n nhỏ. Nếu cần đếm số cặp theo vị trí, map phải lưu tần suất chứ không chỉ một index.

Nếu cần tất cả cặp duy nhất theo giá trị, phải định nghĩa trùng và output. Một map chỉ trả lần đầu không đủ. Nếu dữ liệu stream, hash map cho đáp án ngay khi phần bù đã xuất hiện, nhưng bộ nhớ tăng theo số giá trị.

Từ Two Sum tới 3Sum

3Sum thường sort mảng, cố định i rồi dùng hai con trỏ trên phần còn lại. Chi phí O(n²). Phải bỏ trùng i, l, r để không lặp bộ ba. Dùng hash cho mỗi i cũng O(n²) trung bình nhưng deduplicate output phức tạp hơn.

Đừng nói 3Sum là “Two Sum cộng thêm một vòng” rồi bỏ qua hợp đồng. Bài thường yêu cầu bộ ba giá trị duy nhất, không phải chỉ số đầu tiên; sort giúp chuẩn hóa. Với số lớn, tổng ba phần tử cần kiểu rộng.

Từ 3Sum tới 4Sum và k-Sum

4Sum có thể cố định hai vị trí rồi hai con trỏ O(n³), hoặc chia đôi thành các tổng cặp khi biến thể cho phép. K-Sum đệ quy trên mảng đã sort giảm về Two Sum ở đáy. Cắt nhánh bằng tổng nhỏ/lớn nhất giúp nhanh nhưng phải tránh overflow.

Meet-in-the-Middle cho 4Sum đếm số bộ từ bốn mảng có thể tạo hai danh sách tổng cặp O(n²), rồi ghép phần bù. Cùng ý “phần bù” nhưng cấu trúc dữ liệu và hợp đồng đếm khác Two Sum cơ bản.

Cách trình bày trong phỏng vấn

Bắt đầu: “Vét cạn thử mọi cặp O(n²). Ta đang lặp việc tìm phần bù. Tôi sẽ quét trái sang phải, map chỉ chứa phần tử trước j; trước khi chèn a[j], tìm target-a[j].” Câu này nêu tiến hóa, invariant và lý do thứ tự.

Sau code, chạy 3,3, không có đáp án, số âm, và một ca nhiều đáp án. Nêu O(n) trung bình/O(n) bộ nhớ. Nếu người phỏng vấn hỏi không dùng extra space, đề xuất sort + two pointers và nói tác động lên chỉ số.

Các lỗi khiến lời giải “gần đúng”

• Chèn trước rồi tìm, dùng một phần tử hai lần.
• Lưu bool thay index dù output cần chỉ số.
• Dùng target-x trong kiểu hẹp gây overflow.
• Dùng set và mất quy tắc cặp đầu tiên.
• Sort mảng gốc rồi trả chỉ số sau sort.
• Khẳng định unordered_map luôn O(1) trong mọi trường hợp.
• Không định nghĩa output khi không có đáp án; bản mẫu trả -1 -1.

Tự kiểm bằng vét cạn

Sinh mảng ngắn gồm số âm, 0, trùng; với mỗi target, vét mọi j rồi mọi i<j theo cùng quy tắc. So cặp với hash. Cách này độc lập về thuật toán và bắt cả quy tắc hòa. Random test chỉ đáng tin khi oracle thực sự đơn giản hơn lời giải.

Thử đặc biệt: n=0, n=1, 3 3 target 6, -3 7 3 -7 target 0, và target không tồn tại. Nếu đổi hợp đồng sang bất kỳ cặp, test cũng phải đổi; test không đứng ngoài đặc tả.

Nếu đề yêu cầu cặp nhỏ nhất theo thứ tự từ điển

Quy tắc “trả ngay khi thấy phần bù” tối ưu cho cặp có j nhỏ nhất theo lượt quét, nhưng cần nói rõ cách hòa i. Giữ chỉ số đầu tiên của mỗi giá trị làm i nhỏ nhất cho j đó. Nếu hợp đồng thay thành cặp giá trị nhỏ nhất hoặc mọi cặp, không thể dùng nguyên logic trả sớm.

Hãy viết bốn hợp đồng cạnh nhau: bất kỳ cặp; cặp chỉ số từ điển nhỏ nhất; mọi cặp chỉ số; mọi cặp giá trị duy nhất. Cùng đầu vào nhưng cấu trúc lưu có thể là một index, danh sách index, tần suất hoặc mảng đã sort. Đây là bài tập tốt để thấy thuật toán luôn phục vụ đặc tả, không phục vụ tên “Two Sum”.

Luyện ngay trên Big-O Coding

Giải Two Sum và các bài bảng băm liên quan, rồi thử viết lại bằng sort + hai con trỏ.

Câu hỏi thường gặp

Nguồn tham khảo

• GeeksforGeeks: Pair with given sum
• cppreference: std::unordered_map
• Java 21: HashMap API