Phân tích

Bài toán yêu cầu tìm hai chỉ số ~i < j~ sao cho ~nums[i] + nums[j] = target~.

Tiếp cận ngây thơ (O(N²)): Duyệt mọi cặp ~(i, j)~ với ~i < j~, kiểm tra nếu ~nums[i] + nums[j] = target~. Cách này sẽ TLE với ~N = 10^5~ vì tốn ~5 \times 10^9~ phép tính.

Tiếp cận tối ưu — Bảng băm (O(N)): Duyệt mảng một lần, với mỗi phần tử ~x~ tại chỉ số ~i~:

• Tính ~\text{complement} = target - x~
• Nếu ~\text{complement}~ đã tồn tại trong bảng băm, ta đã tìm thấy cặp cần tìm.
• Ngược lại, lưu ~x \to i~ vào bảng băm và tiếp tục.

Độ phức tạp: ~O(N)~ thời gian, ~O(N)~ bộ nhớ.

Thuật toán

seen = {}  # giá trị -> chỉ số
for i, x in enumerate(nums):
    complement = target - x
    if complement in seen:
        return [seen[complement], i]  (i < j đảm bảo vì seen chứa các phần tử trước i)
    seen[x] = i

Lưu ý: Do ta duyệt từ trái sang phải, khi tìm thấy ~complement~ trong ~seen~, chỉ số của nó luôn nhỏ hơn ~i~, đảm bảo ~i < j~.

Ví dụ truy vết

Với ~nums = [2, 7, 11, 15]~, ~target = 9~:

• ~i=0~: ~x=2~, ~complement=7~, ~seen={}~ → chưa có → ~seen = \{2: 0\}~
• ~i=1~: ~x=7~, ~complement=2~, ~seen = \{2: 0\}~ → tìm thấy! → trả về ~[0, 1]~

Code mẫu (Python)

import sys
input = sys.stdin.readline

def main():
    n, target = map(int, input().split())
    nums = list(map(int, input().split()))
    seen = {}
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            a, b = seen[complement], i
            if a > b:
                a, b = b, a
            print(a, b)
            return
        seen[x] = i

main()

Code mẫu (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; long long target;
    cin >> n >> target;
    vector<long long> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    unordered_map<long long, int> seen;
    for (int i = 0; i < n; i++) {
        long long complement = target - nums[i];
        if (seen.count(complement)) {
            int a = seen[complement], b = i;
            if (a > b) swap(a, b);
            cout << a << " " << b << "\n";
            return 0;
        }
        seen[nums[i]] = i;
    }
    return 0;
}