Two Sum

Cố định chỉ số đầu tiên i rồi thử từng chỉ số j ở bên phải cho đến khi nums[i] + nums[j] bằng target. Bắt đầu j từ i + 1 giúp một vị trí không ghép với chính nó, thử mỗi cặp một lần và đặt chỉ số nhỏ hơn lên trước. Cặp bạn cần là một trong những cặp được thử, nên bạn sẽ tìm thấy nó.

n số tạo thành khoảng n²/2 cặp: n = 10^4 có nghĩa là gần 5 × 10^7 phép cộng.

Với một nums[i] cố định, vòng lặp bên trong của cách vét cạn tìm một giá trị đã biết trước: target - nums[i]. Việc quét đó thực chất là một thao tác tra cứu, còn từ điển băm ánh xạ giá trị sang chỉ số có thể tra cứu trong thời gian hằng số trung bình.

Tra cứu trước, lưu sau. Khi đó, một số chỉ có thể ghép cặp với một số đứng trước nó, không bao giờ với chính nó. Vì số ghép cặp luôn đứng trước nên chỉ số của số đó cũng nhỏ hơn. Mỗi số được duyệt một lần, với các thao tác trên từ điển có thời gian hằng số, nên việc tìm kiếm có độ phức tạp O(n); đổi lại, cần một từ điển có tối đa n mục.