数组求和统计（834764）题解

暴力解法：
枚举l, r，计算区间和，统计有多少对符合条件的l, r

int countLR(vector<int> &a, vector<int> &b) {
        int n = a.size();
        int ans = 0;
        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                int s = 0;
                for (int i = l; i <= r; i++) {
                    s += a[i];
                }

                ans += (s == b[l] + b[r]);
            }
        }
        return ans;
    }

正解：
求出前缀和数组S,S定义如下：

那么当选定数对(l, r)之后，需要满足的条件可变换为：

整理得

那么我们从小到大枚举r，然后对于可行的l，用map统计左边的式子每一种可能的和出现的次数，然后对于每一个r在map中查询有多少个可行的l
在代码中，可以调整坐标的表示使得代码更容易写

int countLR(vector<int> &a, vector<int> &b) {
        int n = a.size();
        vector <int> s(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i - 1];
        }
        map <int, int> cnt;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            cnt[b[i] + s[i]]++;
            ans += cnt[s[i + 1] - b[i]];
        }
        return ans;
    }