数组求和统计_

liuche

看到前面牛人的答案，觉得解释不是很清晰，所以补充一下。用的是python3

首先

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

可以转化为

$\sum_{i=0}^{r}{a_{i}}-\sum_{i=0}^{l}{a_{i}} + a_{l}= b_{r}+b_{l}$ ,要加 $a_{l}$ ，不加的话，等于区间和没有加上。

更进一步，我们可以得到：

$\sum_{i=0}^{r}{a_{i}}-b_{r}=b_{l} + \sum_{i=0}^{l}{a_{i}} - a_{l}$

看到这里可以认为是计算找到使等式F(r)=F(l)-a(l)，成立的r和l。

编辑于 2020-03-30 17:20:32 回复(4)

沧海_微尘

额，没什么技巧，就是暴力，然后避免在遍历一次的时候减少计算，sum++就可。

func countLR( a []int ,  b []int ) int {
    // write code here
    total := 0
    for i:=0;i<len(a);i++{
        sum := 0
        for j:=i;j<len(a);j++{
            sum += a[j]
            if sum == b[i]+b[j]{
                total++
            }
        }
    }
    
    return total
}

发表于 2020-03-19 14:42:10 回复(5)

C/C++

nbgao

class Solution {
public:
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型vector 数组a
     * @param b int整型vector 数组b
     * @return int整型
     */
    int countLR(vector<int>& a, vector<int>& b) {
        int n = a.size(), cnt = 0;
        vector<int> c(n, 0);
        c[0] = a[0];
        for(int i=1;i<n;i++)
            c[i] = c[i-1] + a[i];
        for(int l=0;l<n;l++)
            for(int r=l;r<n;r++){
                if(l==0 && (c[r] == b[l]+b[r]))
                    cnt++;
                else if(l!=0 && (c[r]-c[l-1] == b[l]+b[r]))
                    cnt++;
            }
        return cnt;
    }
};

发表于 2020-08-04 22:16:22 回复(0)

C/C++

卷积神经网络哦

前缀和问题，给的n是1e4，这意味着O(n^2)解是极限了，O(n^3)的解会超时(有些题目测试样例给的太弱，运气好也能过，但并不是正解)

int countLR(vector<int>& a, vector<int>& b) {
    int n = a.size();
    vector<int> tmp = vector<int>(n + 1, 0);
    for(int i = 1; i <= n; i++) tmp[i] += (tmp[i-1] + a[i-1]);
    int res = 0;
    for(int i = 1; i <= n; i++) 
        for(int j = i - 1; j < n; j++) 
            if(tmp[j+1] - tmp[i-1] == b[i-1] + b[j]) res++;
    return res;
}

发表于 2020-05-12 11:54:24 回复(0)

Python 3

ZhongHaoWang

对a数组统计前缀和,假设当前区间为[l,r]，根据题意有pre[r + 1] - pre[l] == bl + br，变换等式为pre[r + 1] - br == bl + pre[l];因此我们倒序遍历b数组,枚举其左边界,同时统计pre[r + 1] - br的个数即可

import collections
class Solution:
    def countLR(self , a , b ):
        # write code here
        pre = [0]
        for i in range(len(a)):
            pre.append(pre[-1] + a[i])
        v = collections.defaultdict(int)
        ans = 0
        for i in range(len(b) - 1,-1,-1):
            v[pre[i + 1] - b[i]] += 1
            cur = b[i] + pre[i]
            ans += v[cur]
        return ans

发表于 2021-08-28 10:29:47 回复(0)

大隐_

Python 暴力破解超时

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算有多少对符合条件的数对
# @param a int整型一维数组 数组a
# @param b int整型一维数组 数组b
# @return int整型
#



class Solution:
    def countLR(self, a, b):
        size = len(a)
        count = 0
        a_sums = [a[0]]
        for i in range(1, size):
            a_sums.append(a_sums[i - 1] + a[i])

        for l in range(size):
            for r in range(l, size):
                if r == l:
                    if a[r] == b[r] + b[l]:
                        count = count + 1
                else:
                    if a_sums[r] - a_sums[l] + a[l] == b[r] + b[l]:
                        count = count + 1
        return count

编辑于 2021-06-02 15:45:20 回复(0)

Java

不过如此Sa

public int countLR (int[] a, int[] b) {
// write code here
int l;
int r;
int n=0;
int asum=0;
int bsum=0;
for(l=0;l<=b.length-1;l++){
for(r=0;r<=b.length-1;r++){
bsum=b[l]+b[r];
asum=leijia(a,l,r);
if(asum==bsum){
n++;
}
}
}
return n;
}

public int leijia(int[] a,int i,int j){
int sum = 0;
while(i<=j){
sum = sum+a[i];
i++;
}
return sum;
}

发表于 2021-05-24 16:43:40 回复(0)

Java

追梦人201910151140798

public int countLR (int[] a, int[] b) {
// write code here

int count = 0;
for(int i = 0; i < b.length; i++){
int sumb = 0;
int suma = 0;
for(int j = i ; j < b.length; j++){
sumb = b[i]+b[j];
suma = suma + a[j];
if(suma == sumb){count++;}
}
}
return (count);
}

发表于 2021-03-09 22:44:22 回复(0)

mawy610

class Solution:
    def countLR(self , a , b ):
        # write code here
        n = len(a)
        res = 0
        s = []
        s.append(a[0])
        for i in range(1, n):
            s.append(s[i-1] + a[i])
        for l in range(n):
            for r in range(l, n):
                if s[r] - s[l] + a[l] == b[l] + b[r]:
                    res += 1
        return res

用前缀和数组把时间降到n²还是不行

发表于 2020-08-22 14:37:10 回复(0)

Java

我济菜狗

利用不符合要求数对产生的信息，记录下差值，避免重复求和

java代码如下：

import java.util.*;


public class Solution {
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型一维数组 数组a
     * @param b int整型一维数组 数组b
     * @return int整型
     */
    public int countLR (int[] a, int[] b) {
        int count = 0;
        
        for(int i = 0;i < a.length;i++){
            int less = a[i]-2*b[i];
            if(less == 0){
                count++;
            }
            for(int j = i+1;j < a.length;j++){
                less += a[j]+ b[j-1]-b[j];
                if(less == 0){
                    count++;
                }
            }
        }
        return count;
    }
}

编辑于 2020-08-16 19:47:01 回复(0)

拿到offer在改名儿

public int countLR (int[] a, int[] b) {
    int[] sum = new int[a.length];
    sum[0] = a[0];
    for (int i = 1; i < a.length; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    int res = 0;
    for (int l = 0; l < a.length; l++) {
        for (int r = l; r < a.length; r++) {
            int curSum = sum[r] - (l - 1 >= 0 ? sum[l -1] : 0);
            int bSum = b[l] + b[r];
            if (curSum == bSum) res++;
        }
    }
    return res;
使用一个求和数组优化时间复杂度。

发表于 2020-08-11 22:40:51 回复(1)

牛客449601568号

func countLR( a []int ,  b []int ) int {
    if len(a)==0||len(b)==0||len(a)!=len(b){
        return 0
    }
    //计算前缀和：sumA[0]=a[0],sumA[1]=a[0]+a[1] ...
    sumA:=make([]int,len(a))
    temp:=0
    for k,v:=range a{
        temp+=v
        sumA[k]=temp
    }  
    result:=0
    target := map[int]int{}
    //由条件1可知：l<=r
    //由条件2可知：  a[l]+a[l+1]+...a[r]=b[l]+b[r]
    //也即是：sumA[r]-sumA[l]+a[l]=b[l]+b[r]
    //移项得：sumA[r]-b[r]=b[l]+sumA[l]-a[l]
    //使用map：target保存所有等式右边的“b[l]+sumA[l]-a[l]”计算结果，以等式右边的值作为k，结果出现的次数作为v。
    //计算等式左边的“sumA[r]-b[r]”值，判断该值在map ：target中是否作为k出现过出现过即表示存在等式成立的情况。
    //因为l<=r，所以讲循环变量l和r可以统一为k，放入同一个for循环。也即是计算等式左边并判断存在性的时机一定在计算等式右边的时机之后或者同时，绝不会在之前。
    for k:=range a{
        target[sumA[k]+b[k]-a[k]]+=1
        if t,ok:=target[sumA[k]-b[k]];ok{
            result+=t
        }
    }
    return result
}
    //此题记录中间结果sumA记录前缀和，使用target记录计算过的值避免重复计算。使得三重循环降低为两次循环。
    //时间复杂度从n^3降低到n。空间复杂度从1增加到n。典型的以空间换时间思路。

发表于 2020-05-25 17:02:25 回复(0)

冷狼201903100855478

import java.util.*;


public class Solution {
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型一维数组 数组a
     * @param b int整型一维数组 数组b
     * @return int整型
     */
    public int countLR (int[] a, int[] b) {
        // write code here

        int suma = 0;
        int sumb = 0;
        int count = 0;
        for (int L = 0; L < a.length; L++) {
            for (int R = L; R < a.length; R++) {
                sumb = b[L] + b[R];
                suma = suma + a[R];
                if(suma == sumb) {
                    count++;
                }
            }
            suma = 0;// 记得在每次L变化的时候，对suma进行置零
            sumb = 0;
        }
       return count;
    
    }
}

发表于 2020-05-24 10:11:38 回复(0)

雪牛牛

class Solution:
	def countLR(self, a, b):
		n = len(a)
		ct = 0
		suml = [i for i in range(n + 1)]
#		left = 0
		suml[0] = 0
		for r in range(1, n + 1):
			suml[r] = suml[r - 1] + a[r - 1]
		for l in range(0, n):
			for r in range(0, l + 1):
				if suml[l+1] - suml[r] == b[r] + b[l]:
					ct += 1
		return ct

Python 的两个loop，只通过45%。求大神帮看看。

发表于 2020-05-08 21:04:59 回复(0)

Sun浅雨

int countLR(vector<int>& a, vector<int>& b) {
    // write code here
    int n = a.size();
    int ans = 0;
    for (int l = 0; l < n; l++) {
        int s = 0;
        for (int r = l; r < n; r++) {
            s += a[r];
            ans += (s == b[l] + b[r]);
        }
    }
    return ans;
}

发表于 2020-05-08 15:09:50 回复(0)

御龙逐日

+ 分析：
    1. 暴力解法当然是可以的，但是时间复杂度肯定很大了，因为一定有重复的被计算过，浪费了计算资源
    2. 使用一个记忆元素来记住规划过的信息
        1. 当然是状态分解：
            我们使用 S_a(R) 表示 a 中的前R个元素和
            sum(a[L:R+1]) = b[L] + b[R]
            ==> S_a(R) - S_a(L) + a[L] = b[L] + b[R]
            ==> S_a(R) - b[R] = S_a[L] + b[L] - a[L]
            ==> ( S_a(R) - b[R] ) = ( S_a(L) - b[L] ) + 2 x b[L] - a[L]
        2. 也就是构造一个 TMP[]，使得里面每一个元素都是 S_a(i) - b[i]
        3. 可以发现：
            1. 当i作为左边界L时，等号右边是一定可以算出来一个value的
            2. 需要判断的是：当i作为右边界R时，等式左边的值是不是能和之前的值对上。
    3. 所以构造一个字典，里面存的是：计算值，这个值的次数
    4. 当i从左向右走的时候：
        1. 先存value：
            + 如果这个value存在过，那么说明不是第一次被计算出来了，所以次数+1；
            + 如果这个value没存在过，说明本次计算是第一次计算，次数是1
        2. 存好了value之后，当i作为右边界时，等式的左边也是有值 value_1 的：
            + 如果 value_1 存在过，说明存在一个l，使得当前i作为右边界时，等式成立，那么count+1
            + 如果value_1 不存在，count就不加

发表于 2020-04-28 21:01:23 回复(0)

Java

QuellanAn

public int countLR (int[] a, int[] b) {
        // write code here
        int count=0;
        for(int i=0;i<b.length;i++){
            int sum=0;
            for(int j=i;j<b.length;j++){
                sum+=a[j];
                if(sum==b[i]+b[j]){
                    count++;
                }
            }
        }
        return count;
    }

暴力求解，竟然没有超时。然而也就想到了暴力求解

发表于 2020-04-28 16:47:11 回复(1)

C/C++

海康内推:4YM8N5

class Solution {
public:
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型vector 数组a
     * @param b int整型vector 数组b
     * @return int整型
     */
    int countLR(vector<int>& a, vector<int>& b) {
        int len = a.size();
        int res = 0;
        for (int l = 0; l < len; l++)
        {
            int sum_l=0;
            int sum_r = 0;
            sum_l += a[l];
            for (int r = l; r < len; r++)
            {
                sum_r += a[r];
                if (sum_l - a[l] + b[l] == sum_r - b[r])
                    res++;
            }
        }
        return res;
    }
};

发表于 2020-04-20 11:31:30 回复(0)

林佳潇

假设我们已经求出了前缀和，对于下标[i,j]而言，要想符合题目中的数对：

需要满足：

pre[j+1]-pre[i]=b[i]+b[j]

移项

pre[j+1]-b[j]=pre[i]+b[i]

所以扫一遍数组，用一个map记录pre[i]+b[i]出现了多少次，然后检查是否已经出现了pre[j+1]-b[j],如果有的话，加在结果中。

class Solution {
public:
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型vector 数组a
     * @param b int整型vector 数组b
     * @return long长整型
     */
    long long countLR(vector<int>& a, vector<int>& b) {
        // write code here
        long long last = 0,ret = 0;
        unordered_map<int, int> p = { {0,0} };
        for (int i = 0; i < a.size(); i++)
        {
            p[last + b[i]]++;
            last += a[i];
            if (p.count(last - b[i]))
                ret += p[last - b[i]];
        }
        return ret;
    }
};

发表于 2020-04-17 17:16:19 回复(1)

古学冬

import java.util.*;

public class Solution {
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型一维数组 数组a
     * @param b int整型一维数组 数组b
     * @return int整型
     */
    public int countLR (int[] a, int[] b) {
        // write code here
        int result = 0;
        for (int i = 0; i < a.length; ++i) {
            int sum = 0;
            for (int j = i; j < a.length; ++j) {
                sum += a[j];
                if (sum == b[i] + b[j]) {
                    result++;
                }
            }
        }
        return result;
    }
}

发表于 2020-04-16 17:56:55 回复(0)

数组求和统计

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题