题解 | #数组求和统计#

题目链接

首先理解题意:
是否存在数组a的区间[l,r]的和 等于 b[l] + b[r]?
方法一:容易想出暴力解***超时)
		int len = a.length;
        int res = 0;
        for(int l = 0; l < len; l++) {
            for(int r = l; r < len; r++) {
                int s = 0;
                for(int i = l; i <= r; i++) {
                    s += a[i];
                }
                if(s == b[l] + b[r]) res += 1;
            }
        }
        return res;
方法二:计算出每个数组a的区间和， 方法一超时是因为太多的重复计算，方法二将各个从头至尾的区间已求出。\n

举个例子:如果想知道数组a的区间[1,3]的区间和，只需要将算一次  sumArr[r] - sumArr[l] + a[l] 解决了大量的重复计算！

		int res = 0;
        int len = a.length;
        int[] sumArr = new int[len];
        
        for(int i = 1; i < len; i++) {
            sumArr[i] = sumArr[i-1] + a[i];
        }
        
        for(int l = 0; l < len; l++) {
            for(int r = l; r < len; r++) {
                if(sumArr[r] - sumArr[l] + a[l] == b[l] + b[r]) res++;
            }
        }
        return res;