求数组任意连续一部分和大于某个数的算法

Question

假设一个数组长度为100
连续长度定为10
参考值为 x

如果array[0]~array[9] 的和大于x ，则array[0]是想要的点
如果array[1]~array[10] 的和大于x ，则array[1]也是想要的点
。。。。。。
如果array[y]~array[y+9] 的和大于x ，则array[y]也是想要的点

找出所有的点

Answer 1

需求只是array[0]+...+array[9]>x么?

golang版本

// data int数组 l长度 x 参考值
func test(data []int, l, x int) []int {
    result := []int{}
    len := len(data)
    if len < l {
        return result
    }
    sum := 0
    for i := 0; i < l; i++ {
        sum += data[i]
    }
    if sum > x {
        result = append(result, 0)
    }
    for i := l; i < len; i++ {
        sum = sum + data[i] - data[i-l]
        if sum > x {
            result = append(result, i-l+1)
        }
    }
    return result
}

思路就是先把前l个加起来判断是否大于x，然后sum加一个新的，减掉一个老的，在判断是否大于x,循环一次O(n)

Answer 2

思路与楼上一致。C实现。

void func(int *array,int x)
{
    int i;
    int sum=0;
    for(i=0;i<10;i++)
        sum+=array[i];
    if(sum>x)
        printf("array[0]=%d\n",array[0]);

    for(i=1;i<=90;i++)
    {
        sum=sum-array[i-1]+array[i+9];
        if(sum>x)
            printf("array[%d]=%d\n",i,array[i]);
    }
}

Answer 3

扫面一遍数组array，计算出一个新数组sum_array,其中sum_array[i+1] = array[0]+ .. + array[i]（sum_array[0] = 0）;
扫描一遍sum_array[i],找出所有的i, sum_array[i + 10] -sum_array[i] == x, 则i为满足条件的点。