Chỉ số cân bằng (Equilibrium Index) của mảng trong C++

Trong bài toán này, cho mảng arr[] gồm n số nguyên. Nhiệm vụ là tìm chỉ số cân bằng (Equilibrium Index) của mảng.

Chỉ số cân bằng là chỉ số e sao cho tổng các phần tử bên trái (từ 0 đến e-1) bằng tổng các phần tử bên phải (từ e+1 đến n-1).

Công thức: sum(arr[0...e-1]) = sum(arr[e+1...n-1])

Ví dụ minh họa

Đầu vào: arr[] = {5, 1, 2, 8, 3, 4, 1}

Đầu ra: 3

Giải thích:

arr[0] + arr[1] + arr[2] = 5 + 1 + 2 = 8
arr[4] + arr[5] + arr[6] = 3 + 4 + 1 = 8

Phương pháp giải

Cách 1: Vét cạn O(N²) - Duyệt từng chỉ số, tính tổng trái và tổng phải bằng vòng lặp lồng. (Như code gốc).

Cách 2: Tối ưu O(N) - Tiền tố (Prefix Sum) - Tính tổng cả mảng trước. Duyệt một lần, cập nhật tổng bên trái, tổng bên phải = Tổng cả mảng - Tổng trái - Phần tử hiện tại.

Chương trình minh họa (Tối ưu O(N))

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

int findEquilibriumIndex(int arr[], int n) {
    long long totalSum = 0;
    for (int i = 0; i < n; i++) totalSum += arr[i];

    long long leftSum = 0;
    for (int i = 0; i < n; i++) {
        // Tổng bên phải = Tổng tất cả - Tổng trái - Phần tử hiện tại
        long long rightSum = totalSum - leftSum - arr[i];
        if (leftSum == rightSum)
            return i;
        leftSum += arr[i];
    }
    return -1; // Không tìm thấy
}

int main() {
    int arr[] = {5, 1, 2, 8, 3, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int idx = findEquilibriumIndex(arr, n);
    if (idx != -1)
        cout << "Chỉ số cân bằng là " << idx;
    else
        cout << "Không có chỉ số cân bằng";
    return 0;
}

Đầu ra

Chỉ số cân bằng là 3