Đếm cặp trong mảng đã sắp xếp có tổng nhỏ hơn x trong C++

Giới thiệu

Cho mảng đã sắp xếp và số x. Đếm số cặp (i, j) với i < j sao cho arr[i] + arr[j] < x.

Ví dụ

• arr = [2,7,1,0,8] (sắp xếp: [0,1,2,7,8]), x = 8 → 4 cặp
• arr = [2,4,6,8], x = 10 → 2 cặp (2,4), (2,6)

Các cách tiếp cận

Cách 1: Naive O(n²)

Duyệt tất cả cặp, kiểm tra tổng.

Cách 2: Hai con trỏ (Two Pointers) O(n)

left = 0, right = n-1:

• Nếu arr[left] + arr[right] < x: tất cả cặp (left, left+1...right) thỏa → cộng right-left, left++
• Ngược lại: right--

Ví dụ triển khai (C++)

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

// Cách 1: Naive
int countSumPairsNaive(vector<int> arr, int x) {
    int count = 0, n = arr.size();
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (arr[i] + arr[j] < x) count++;
    return count;
}

// Cách 2: Two Pointers
int countSumPairsTwoPtr(vector<int> arr, int x) {
    sort(arr.begin(), arr.end());
    int count = 0, left = 0, right = arr.size() - 1;
    while (left < right) {
        if (arr[left] + arr[right] < x) {
            count += right - left;
            left++;
        } else {
            right--;
        }
    }
    return count;
}

int main() {
    vector<int> arr = {0, 1, 2, 7, 8};
    int x = 8;
    cout << "Naive: " << countSumPairsNaive(arr, x) << endl;   // 4
    cout << "TwoPtr: " << countSumPairsTwoPtr(arr, x) << endl;  // 4
    return 0;
}

Đầu vào

[0,1,2,7,8], x=8

Đầu ra

4