题解 | #数组求和统计#

题目描述
牛牛有两个长度为n的数组a,b,牛牛希望统计有多少数对(l,r)满足：
1、0<=l<=r<=n-1
2、 $图片说明$

方法一：暴力方法

求解思路
对于求解本题目，我们使用内外层指针来进行暴力循环求解。让外层指针遍历数组a中的每个元素，内层指针遍历外层指针以后的在数组a中的元素并且累加。同时将累加和与内外层指针在数组b中对应位置元素之和作比较，若相等，则计数+1.

图片说明

解题代码

class Solution {
public:
    int countLR(vector<int>& a, vector<int>& b) {
        int hycount = 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]) // 比较首尾
                    hycount++;
            }
        }
        return hycount; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：优化--前缀的思想

求解思路
对于方法一我们对其进行优化，在方法一的代码中我们发现题目所给的公式并非每次都从头加到尾，而是在前缀的基础上，加上当前元素，我们可以用dp[i]表示前i个元素的前缀和。

图片说明

解题代码

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

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用哈希表，引入额外的内存地址空间，因此空间复杂度为 $O(N)$