Đếm cặp có tổng cho trước trong C++

Cho mảng và số sum. Đếm số cặp (i,j) (i < j) có tổng bằng sum.

Ví dụ: {2,8,1,5,11}, sum=10 → 2 (cặp (2,8) và (5,5) nếu có, thực tế là (2,8) và (8,2) nhưng i

Giải thuật: Vòng lặp lồng O(n^2). Có thể tối ưu bằng hash map O(n).

Ví dụ

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

int Pair_Sum(int arr[], int size, int sum) {
    int count = 0;
    for (int i = 0; i < size; i++)
        for (int j = i+1; j < size; j++)
            if (arr[i] + arr[j] == sum) count++;
    return count;
}

int main() {
    int arr[] = {2,6,1,7,9,8};
    int sum = 9;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << Pair_Sum(arr, size, sum);
    return 0;
}

Đầu ra

Count of pairs with given sum 9 is: 2