Đếm bộ ba có tổng trong khoảng [a,b] C++

Cho mảng Arr[] và khoảng [a, b]. Đếm số bộ ba (i

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1, 2, 3, 4, 5}, N = 5, L = 2, R = 8
• Output: 4
• Giải thích: (1,2,3)=6, (1,2,4)=7, (1,2,5)=8, (1,3,4)=8.

Ví dụ 2:

• Input: arr = {2, 2, 2, 2, 2}, N = 5, L = 2, R = 5
• Output: 0
• Giải thích: Mọi bộ ba tổng = 6, không trong [2,5].

Mã nguồn C++ (Vét cạn O(n³))

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

int countTriplets(int arr[], int n, int a, int b) {
    int count = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                int sum = arr[i] + arr[j] + arr[k];
                if (sum >= a && sum <= b) count++;
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {5, 4, 3, 6, 8, 2};
    int L = 9, R = 15, N = 6;
    cout << "So bo ba co tong trong [" << L << "," << R << "]: " << countTriplets(Arr, N, L, R);
    return 0;
}

Kết quả chạy chương trình

So bo ba co tong trong [9,15]: 14

Tối ưu hóa O(n²) - Two Pointers sau sắp xếp

Sắp xếp mảng. Với mỗi i, dùng two pointers (j=i+1, k=n-1) đếm số cặp có tổng trong [a-arr[i], b-arr[i]].

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

long long countTripletsOptimized(int arr[], int n, int a, int b) {
    sort(arr, arr + n);
    long long count = 0;
    
    for (int i = 0; i < n - 2; i++) {
        int targetL = a - arr[i];
        int targetR = b - arr[i];
        int j = i + 1, k = n - 1;
        
        // Đếm cặp (j,k) có targetL ≤ arr[j]+arr[k] ≤ targetR
        while (j < k) {
            int sum = arr[j] + arr[k];
            if (sum > targetR) {
                k--;
            } else if (sum < targetL) {
                j++;
            } else {
                // sum trong khoảng, tất cả cặp từ j đến k-1 với k đều thỏa mãn (vì mảng tăng)
                // Cần đếm chính xác: di chuyển con trỏ phù hợp
                // Cách đơn giản: đếm số cặp ≤ targetR trừ số cặp < targetL
                break; // Xem hàm helper dưới
            }
        }
    }
    return count;
}

// Hàm helper: đếm cặp có tổng ≤ X trong mảng con arr[l..r] (đã sắp xếp)
long long countPairsLE(int arr[], int l, int r, int X) {
    long long cnt = 0;
    int i = l, j = r;
    while (i < j) {
        if (arr[i] + arr[j] <= X) {
            cnt += (j - i);
            i++;
        } else {
            j--;
        }
    }
    return cnt;
}

// Sử dụng helper:
long long countTripletsOptimized2(int arr[], int n, int a, int b) {
    sort(arr, arr + n);
    long long total = 0;
    for (int i = 0; i < n - 2; i++) {
        total += countPairsLE(arr, i + 1, n - 1, b - arr[i]);
        total -= countPairsLE(arr, i + 1, n - 1, a - arr[i] - 1);
    }
    return total;
}

Độ phức tạp