题解 | #数组求和统计#

数组求和统计

http://www.nowcoder.com/practice/efc16ce46397436a8d1a0008c52093c1

数组求和统计

问题描述：牛牛有两个长度为$n$的数组$a$,$b$，牛牛希望统计有多少数对$(l,r)$满足：

$0\leq l\leq r \leq n-1$

$\sum_{i=l}^{r}x_{i}=b_{l}+b_{r}$

示例

输入：[1,2,3,4],[2,1,4,5]

返回值：4

说明：满足条件的数对有$(0,1),(0,2),(1,1),(1,2)$，即存在这样四个等式:

$\sum_{i=0}^{1}x_{i}=b_{0}+b_{1}$

$\sum_{i=0}^{2}x_{i}=b_{0}+b_{2}$

$\sum_{i=1}^{1}x_{i}=b_{1} +b_{1}$

$\sum_{i=1}^{2}x_{i}=b_{1} +b_{2}$

方法一

思路分析

此题我们可以直接使用暴力搜索的办法，即设置内外两层循环，也可理解为快慢指针，循环计算数组$a$中$i(i<n)$位置到$j$位置$(i<=j<=n-1)$之间的元素的和，并计算数组$b$中$b[i]+b[j]$的和，判断两者是否相等，如果相等那么统计数对的变量加一。

图解

输入：[1,2,3,4],[2,1,4,5]

其中 $sum=\sum_{k=i}^{j}x_{k}$ ，内外两层循环暴力搜索。

$i=0$
$j$	0	1	2	3
$sum$	1	3	6	10
$b[i]+b[j]$	4	3	6	7
$ans$		$ans++$	$ans++$
数对		$(0,1)$	$(0,2)$

$i=1$
$j$	1	2	3
$sum$	2	5	9
$b[i]+b[j]$	2	5	6
$ans$	$ans++$	$ans++$
数对	$(1,1)$	$(1,2)$

$i=2$
$j$	2	3
$sum$	3	7
$b[i]+b[j]$	8	9
$ans$
数对

$i=3$
$j$	3
$sum$	4
$b[i]+b[j]$	10
$ans$
数对

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 n=a.size();
        int sum;
        int res=0;
        for(int i=0;i<n;i++)
        {
            sum=0;
            for(int j=i;j<n;j++)
            {
                sum+=a[j];//数组a中[i,j]之间元素的和
                if(sum==(b[i]+b[j]))//数组a中[i,j]之间元素的和是否与数组下标为i和j的元素和相同
                    res++;
                
            }
            
        }
        return res;
    }
};

复杂度分析

时间复杂度：内外两层循环，循环次数为$1+2+3+...+n=n*(n+1)/2$，因此时间复杂度为$O(n^2)$
空间复杂度：借助于两个变量，因此空间复杂度为$O(1)$

方法二

思路分析

注意到方法一中时间消耗在了计算数组$a$中$i,(i<n)$i位置到$j$位置$(i<=j<n)$之间的元素的和上面，因此方法二中先将数组$a$的前缀和计算并将其存储在数组$a$中，那么就有然后利用下面的公式推导。

$a_{r}=\sum_{i=0}^{r}x_{i}, a_{l-1}=\sum_{i=0}^{l-1}x_{i}\\ \Downarrow \\\sum_{i=l}^{r}x_{i}=b_{l}+b_{r} (1)\\ \Downarrow \\ \sum_{i=0}^{r}x_{i}-\sum_{i=0}^{l-1}x_{i}=b_{l}+b_{r} (2)\\\Downarrow\\ \sum_{i=0}^{r}x_{i}-b_{r}=\sum_{i=0}^{l-1}x_{i}+b_{l} (3) \\\Downarrow\\ a_{r}-b_{r}=a_{l-1}+b_{l}(4)$

因此循环遍历数组$b$，设置map对象计算$(4)$右边 $a_{l-1}+b_{l}$ 的值的数量，即 $a_{l-1}+b_{l}$ 作为键值， $map[a_{l-1}+b_{l} ]$ 键值对应的数量。

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
       for(int i = 1; i < a.size(); i++)
            a[i] += a[i-1];//计算数组a的前缀和并存储在数组a中节省空间
        
        int ans = 0;  
        map<int, int> count;
        count[b[0]] = 1;
        for(int i = 1; i < b.size(); i++) {
            count[b[i]+a[i-1]]++;//等式左边
            ans += count[a[i]-b[i]];//计数等式右边
        }
        return ans;
    }
};