题解 | #数组求和统计#

题目：数组求和统计
描述：牛牛有两个长度为n的数组a,b，牛牛希望统计有多少数对(l,r)满足：
1， $0≤l≤r≤n−1$
2， $图片说明$
示例1：输入：[1,2,3,4],[2,1,4,5]，返回值：4
说明：满足条件的数对有(0,1),(0,2),(1,1),(1,2)
示例2：输入：[0,0,1,1,1],[2,0,4,3,3]，返回值：2

解法一：
思路分析：首先分析题目，笔者认为有人可能看见题目以后会有疑问，不明白题目是什么意思，所以先解释一遍题目，存在两个数组a和b，a和b的数组长度均为n，牛牛统计有多少数对满足两个条件，第一个条件就不进行解释，第二个条件为：
$图片说明$
——这儿的i表示一个代数，l和r表示序号，公式的前半部分为数组a中元素序号从l到r相加的和等于bl和br的和，bl为数组b中序号为l的元素，br为数组b中序号为r的元素。我们以实例1进行分析：数组a为[1，2，3，4]，数组b为[2，1，4，5]，当初始数组a中的l = 0，r = 1时，说明
$图片说明$
——而后半部分，数组b中
$图片说明$
——所以该数对（0，1）表示符合题目要求，可以输出，通过这种方式依次进行判断即可得到最终的结果。
——通过上述分析和描述，我们懂得了题目的含义，在此我们首先想到的肯定是暴力法分析，所以进行代码的描述，我们可以设置三个指针变量l，r和i，l表示从0开始遍历元素，r表示从l的位置开始遍历元素，i表示从l开始遍历，到r结束遍历，设置一个res变量用于返回加起来的结果，然后进行比较判断，当res == b[l] + b[r]的时候，就令count进行累加，最终就可以输出结果，但是暴力法使用的时间太长，如果数据过大，会导致时间运行过长，最终无法正常输出答案。
实例分析：输入：[1,2,3,4],[2,1,4,5]
图片说明
C++核心代码：

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
        int len = a.size();
        int count = 0;//记录最终成功的次数
        for (int l = 0; l < len; l++) {//先搞一个嵌套循环
            for (int r = l; r < len; r++) {
                int res = 0;
                for (int i = l; i <= r; i++) {//将a中累加的结果计算出来
                    res += a[i];
                }
                count += (res == b[l] + b[r]);//如果相等的话就进行次数加1操作
            }
        }
        return count;
    }
};

——因为需要进行两个for循环，每一次循环均为数组a和b的长度N，所以两次for循环的时间复杂度为 $O(N^2)$ ,第三个for循环需要平均循环 $图片说明$ ,所以其时间复杂度为 $O(N^2)$ ，在该算法中不占用内存空间，所以其空间复杂度为 $O(1)$ 。
解法二：
思路分析：通过解法一，我们已经明白该题的规则，在解法一中，其实并不需要从头到尾进行累加，这样只会增加循环的次数，我们可以在已有前缀的基础上加上当前元素进行判断，ai的累加和实际上等同于r的前缀和减去l的前缀和加上al的值，通过计算我们可以得到一个判断的条件，也就是a的前r项和b的第r项的差值等同于a的前l项与b的第l项和a的第l项的差值通过这个条件，我们便可以在遍历的时候加入哈希表，只需要检查a的前r项和b的第r项的差值是否在哈希表中即可。
C++核心代码为：

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
        unordered_map<int,int> map;//建立一个哈希表对象
        int res = 0;//存储对象
        for(int i = 0;i < a.size();i++){
            a[i] += a[i-1];//计算a中的累加和
        }
        map[b[0]]++;
        for (int i = 1; i < a.size(); ++i)//循环判断数组a与数组b的关系
        {
            map[b[i] + a[i - 1]]++;
            int val = a[i] - b[i];//计算两者的差值
            if (map.find(val) != map.end())//判断哈希表中是否存在该数值
            {
                res += map[val];
            }
        }
        return res;
    }
};

——因为在该算法中只需要将数组a的前缀和通过for循环计算出来，在通过一个for循环判断即可，所以其时间复杂度为 $O(N)$ ，在该算法中有一个哈希表对象，用来存储和判断，所以其空间复杂度为 $O(N)$ 。