java - 在最短的时间内计算数组的连续子数组的总和

Question

这是我的代码:

long sum(int[] arr) {
    long sum=0;
    int j,k;
    long sumtoadd;
    for (int i = 0; i < arr.length; i++)
    {
        for (j = i; j < arr.length; j++)
        {
            sumtoadd = 0;
            for (k = i; k <= j; k++)
            {
                sumtoadd = sumtoadd + arr[k];
            }
            sum = sumtoadd + sum;
        }
    }
    return sum;
}

示例:

Array : {1,2,3} Output: 20

Array : {1,1,1} Output: 10

我正在尝试查找数组的所有连续子数组的总和，但对于某些情况，时间超出了。 此解决方案适用于除大型案例之外的所有案例。是否有更好的解决方案？

Answer 1

public class Test1 {

static long sum2(int[] arr) {
    long n = arr.length;
    long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += (n-i)*(i+1)*arr[i];
    }
    return sum;
}

static int[] arr1 = new int[]{1,2,3,4,5,6,7,8,9};
static int[] arr2 = new int[]{1,1,1,1};

public static void main(String[] args) {
    System.out.println("sum(arr1) = " + sum(arr1));
    System.out.println("sum2(arr1) = " + sum2(arr1));
    System.out.println("sum(arr2) = " + sum(arr2));
    System.out.println("sum2(arr2) = " + sum2(arr2));
}

//your code to check
static long sum(int[] arr) {
    long sum=0;
    int j,k;
    long sumtoadd;
    for (int i = 0; i < arr.length; i++)
    {
        for (j = i; j < arr.length; j++)
        {
            sumtoadd = 0;
            for (k = i; k <= j; k++)
            {
                sumtoadd = sumtoadd + arr[k];
            }
            sum = sumtoadd + sum;
        }
    }
    return sum;
}

}