Skip to main content

Practice · 3 of 5

Đếm cặp có tổng bằng S

CHALLENGE
Difficulty: intermediate+25 XP

**Bài toán.** Mảng n phần tử và số S. Đếm số cặp chỉ số (i, j) với i < j và a[i] + a[j] = S. **Ràng buộc:** 1 ≤ n ≤ 2·10^5; 0 ≤ a[i], S ≤ 10^9. Đáp án tới n(n−1)/2 — long long. Sort rồi đếm theo NHÓM BẰNG NHAU: hai nhóm khác nhau ghép chéo cnt[v]·cnt[w]; nhóm v = S/2 tự ghép C(v, 2) = cnt·(cnt−1)/2. Đếm naive hai vòng O(n^2) quá hạn.

Back to lesson: Practice: Synthesis Problem Set