题解 | #数组求和统计#

思路：

题目的主要信息：

两个长度相同的数组a与b，长度都为n
统计数对 $(l,r)$ 出现的次数，其中：

$0 <= l < r <= n - 1$
$\Sigma^{r}_{i=l}a_i=b_l+b_r$

相当于是相同的下标，a数组中的区间求和等于b数组中两端相加。

方法一：暴力法
具体做法：
一个慢指针遍历a数组中的每个元素，另一个快指针遍历a数组中后面的所有元素，并累加快慢指针之间的和，并每次与快慢指针下标在b数组中对应两个元素的和作比较，若是相等则计数加一。

class Solution {
public:
    int countLR(vector<int>& a, vector<int>& b) {
        int count = 0; //计数
        for(int i = 0; i < a.size(); i++){
            int sum = 0;
            for(int j = i; j < a.size(); j++){ //遍历之后的相加
                sum += a[j];
                if(sum == b[i] + b[j]) //比较首尾
                    count++;
            }
        }
        return count;
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，两层循环遍历
空间复杂度： $O(1)$ ，无额外空间

方法二：前缀和+哈希表
具体做法：
对于这个公式： $\Sigma^{r}_{i=l}a_i=b_l+b_r$ ，我们可以看到在方法一中，我们并非每次都从头加到尾，而是在前缀的基础上加上当前元素，我们可以用 $dp[i]$ 表示前i个元素的前缀和。因此这个公式我们还可以变化一下：（下标从1开始）

$\Sigma^{r}_{i=l}a_i=dp[r] - dp[l] + a_l$
$=\Sigma^{r}_{i=1}a_i - \Sigma^{l}_{i=1}a_i + a_l =b_l+b_r$

寻找左右两个前缀和之间的关系，就为：

$\Sigma^{r}_{i=1}a_i - b_r = \Sigma^{l}_{i=1}a_i + b_l - a_l$

因此我们可以在遍历的时候将 $\Sigma^{l}_{i=1}a_i + b_l - a_l$ 放入一个哈希表中，每次检查 $\Sigma^{r}_{i=1}a_i - b_r$ 是否在哈希表中有存在，若是有则加上哈希表中的计数。
图片说明

class Solution {
public:
    int countLR(vector<int>& a, vector<int>& b) {
        int count = 0; //计数
        vector<int> dp; //记录前缀和,dp[i]表示前面项加起来的和
        unordered_map<int, int> mp;
        int sum = 0;
        for(int i = 0; i < a.size(); i++){ //求前缀和
            sum += a[i];
            dp.push_back(sum);
        }
        mp[b[0] + dp[0] - a[0]] = 1; //第0个元素
        for(int i = 1; i < a.size(); i++){
            mp[b[i] + dp[i] - a[i]]++;
            if(mp.find(dp[i] - b[i]) != mp.end())  //在哈希表中查找
                count += mp[dp[i] - b[i]];
        }    
        return count;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，两次遍历都是单循环，unordered_map的查找为 $O(1)$
空间复杂度： $O(n)$ ，哈希表与记录前缀和的辅助数组dp