前缀和_牛客博客

思路：一般想法是直接暴力，但是直接暴力的话每次都需要计算 $\sum_{i=l}^r a_i$ ，于是可以想到创建 a 的前缀和数组 sumA，则 $\sum_{i=1}^r a_i = sumA[r] - sumA[l] + a_l$

class Solution {
public:
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型vector 数组a
     * @param b int整型vector 数组b
     * @return int整型
     */
    int countLR(vector<int>& a, vector<int>& b) {
        // write code here
        vector<long long> sumA;
        long long tmp1 = 0;
        for(auto i: a){
            tmp1 += i;
            sumA.push_back(tmp1);
        }
        int size = a.size();
        int ans = 0;
        for(int i = 0; i < size; i++){
            for(int j = i; j < size; j++){
                if(sumA[j] - sumA[i] + a[i] == b[j] + b[i]){
                    ans++;
                }
            }
        }
        return ans;
    }
};

更新 2020年4月11日15:29:18
看了前面更快的解法，这里介绍下思路
首先还是一样，先建立前缀和数组。然后改写下等式

$\sum_{i=l}^{r}a_i = \sum_{i=0}^{r}a_i - \sum_{i=0}^{l}a_i + a_l = b_l + b_r$

移项得

$\sum_{i=0}^{r}a_i - b_r = \sum_{i=0}^{l}a_i + b_l - a_l$

所以，我们只需将等式右边的结果全部存在 map（C++）、dict（Python）中，然后遍历左边，查询是否有相等的结果即可

class Solution {
public:
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型vector 数组a
     * @param b int整型vector 数组b
     * @return int整型
     */
    int countLR(vector<int>& a, vector<int>& b) {
        // write code here
        vector<long long> sumA;
        map<long long, long long> tmp;
        long long tmp1 = 0;
        for(auto i: a){
            tmp1 += i;
            sumA.push_back(tmp1);
        }
        int size = a.size();
        tmp[b[0] + sumA[0] - a[0]];
        int ans = 0;
        for(int i = 1; i < size; i++){
            tmp[b[i] + sumA[i] - a[i]]++;
            long long val = sumA[i] - b[i];
            if(tmp.find(val) != tmp.end()){
                ans += tmp[val];
            }
        }
        return ans;
    }
};