我要招人

去企业版

首页 > 试题广场 >

数组求和统计

[编程题]数组求和统计

热度指数：13414 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

2， $\sum_{i= l}^{r}{a_i} = b_l + b_r$

示例1

输入

[1,2,3,4],[2,1,4,5]

输出

说明

满足条件的数对有

示例2

输入

[0,0,1,1,1],[2,0,4,3,3]

输出

备注:

算法知识视频讲解

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)

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)

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)

Java

下意识的

import java.util.*;


public class Solution {
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型一维数组 数组a
     * @param b int整型一维数组 数组b
     * @return int整型
     */
public class Solution {
    /**
     * 计算有多少对符合条件的数对
     * @param a int整型一维数组 数组a
     * @param b int整型一维数组 数组b
     * @return int整型
     */
    public int countLR (int[] a, int[] b) {
        // write code here
        if(a==null||a.length==0)
            return 0;
        int n = a.length;
        int count = 0;
        int sumA = 0;
        for(int l=0;l<=n-1;l++){
            sumA += a[l];
            int sumB = 0;
            for(int r=l;r<n;r++){
                if(r!=l)
                    sumB += a[r];
                if(sumA+sumB==(b[l]+b[r]))
                    count++;
            }
            sumA -= a[l];
        }
        return count;
    }

}

暴力解法，符合两个条件就行

编辑于 2020-04-09 17:41:46 回复(0)

Java

海之Zi

纯暴力遍历
    public int countLR (int[] a, int[] b) {
        // write code here
        int res = 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]) {
                    res++;
                }
            }
        }
        return res;
    }

发表于 2020-04-02 11:13:33 回复(0)

Java

satchmo

本题最容易想到的就是遍历，然鹅，当直接按照题中所给的条件进行遍历的话，每一次比较都要计算a[l]到a[r]的元素的和，这样做的结果就是计算复杂度太高，超出时间规定。

于是换一种计算方法，将a中的每个元素之前的和都先计算出来，并且放入一个新数组中。每次遍历比较时只需要计算新数组中 l 和 r 两个位置的差值，即为a[l]到a[r]的元素的和。代码如下：

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 n = a.length;
        int[] sum = new int[n];
        sum[0] = a[0];
        for(int i=1; i<n; i++){
            sum[i] = sum[i-1]+a[i];
        }

        int count = 0;
        for(int l=0; l<n; l++){
            for(int r=l; r<n; r++){
                if(r==l){
                    if(a[r] == b[r]+b[l]){
                        count++;
                    }
                }else if(l<r){
                    if(sum[r]-sum[l]+a[l] == b[r]+b[l]){
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

发表于 2020-03-13 16:26:40 回复(1)