思路:一般想法是直接暴力,但是直接暴力的话每次都需要计算 ,于是可以想到创建 a 的前缀和数组 sumA,则

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
看了前面更快的解法,这里介绍下思路
首先还是一样,先建立前缀和数组。然后改写下等式

移项得

所以,我们只需将等式右边的结果全部存在 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;
    }
};