arrays - 给定一个正整数数组，找到长度为 L 且总和等于 S 的连续子序列的起始索引

Question

给定一个正整数数组，其值在 [1, 8] 中，我想找到长度为 L 的连续子序列的起始索引，它们的总和等于 S。此查询可以表示为 Q< L， S>。示例如下:

A: [3, 2, 3, 1, 2, 1, 3, 1, 1, 6, 3, 3, 3, 2, 3, 1, 1, 3]  
Q< 3, 5 > : [5, 6, 14, 15] ;  
Starting at index 5:  {1, 3, 1},  
Starting at index 6:  {3, 1, 1},  
Starting at index 14: {3, 1, 1},  
Starting at index 15: {1, 1, 3}

Q< 4, 9 > : [0, 12] ;  
Starting at index 0:  {3, 2, 3, 1},  
Starting at index 12: {3, 2, 3, 1}  

查询的结果可以在 O(n) 时间内简单地计算出来。有没有办法通过预处理数组在 O(1) 或 O(log n) 时间内找到这些索引？预处理后的数组数据结构的空间复杂度最好不要超过O(n)。

Answer 1

您可以构建一个求和数组以在 O(n) 时间内找到 L 个连续元素的总和。

A: [3,2,3,1,2,1,3,1]
S: [3,5,8,9,11,12,15,16]

现在对于 A 中的每个元素 i，您可以通过 S[i+L]-S[i] 找到它的总和。总体复杂度为 O(n)。

    int n = 9;
    int a[] = {0,3,2,3,1,2,1,3,1};
    int l = 3;
    int sum = 5;
    int s[] = new int[n];

    s[0] = a[0];
    for(int i=1;i<n;i++)
    {
        s[i] = a[i]+s[i-1];
    }
    for(int i=0;i<n-l;i++)
    {

        int cur = s[i+l]-s[i];

        if(cur == sum)
        {
            System.out.println(cur);
        }
    }