问题

我有一个数字数组，现在我想找到所有连续子数组的和，其值与小于等于 k。我想返回最大的子数组大小。

这是我的程序：

public static int process(List<Integer> arr, int k) {
    int size = 0;
    for (int i = 0; i < arr.size(); i++) {
        int sum = 0;
        for (int j = i; j < arr.size(); j++) {
            sum += arr.get(j);
            if (sum <= k) {
                size = Math.max(size, j - i + 1);
            }
        }
    }
    return size;
}

约束条件:

• 数组大小在1到100000之间。
• 数组元素在1到100之间。
• k 在1到1000000之间。

解释:

Arrays.asList(2, 3, 5, 1, 1, 2, 1), 7

arr = 2, 3, 5, 1, 1, 2, 1

k = 7

可能的子数组：

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

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

[5,1,1], [1,1,2], [1,2,1]

[1,1,2,1]

最大子数组是 [1,1,2,1] = 长度为4。因此，程序应返回4。

上周我在一场竞争性考试中得到了这个任务，当我使用这段代码时，它只通过了50%的测试用例。对于一些隐藏的测试用例，它未能产生正确的输出，还有一些测试用例提示超时问题。

我的代码有什么问题？

**更新:**
稍微修改了我的代码，并添加了一个示例。

<details>
<summary>英文:</summary>

I have an array of numbers, now I want to find all the consecutive subarray sums whose value matches with less than or equal to k. I want to return the largest subarray size.

This is my program:



    public static int process(List&lt;Integer&gt; arr, int k) {
        int size = 0;
        for (int i = 0; i &lt; arr.size(); i++) {
            int sum = 0;
            for (int j = i; j &lt; arr.size(); j++) {
                sum += arr.get(j);
                if (sum &lt;= k) {
                    size = Math.max(size, j - i + 1);
                }
            }
        }
        return size;
    }
	
**constraints:**

    arr size is between 1 to 100000
    array elements are between 1 to 100
    k is between 1 to 1000000
    	

**Explanation:**

    Arrays.asList(2, 3, 5, 1, 1, 2, 1), 7
    
    arr = 2, 3, 5, 1, 1, 2, 1
    
    k= 7

possible sub arrays:

    [2], [3], [5], [1], [1], [2], [1]
    
    [2,3], [5,1], [1,1], [1,2], [2,1]
    
    [5,1,1], [1,1,2], [1,2,1]
    
    [1,1,2,1]
    
    Maximum sub array is [1,1,2,1] = its length is 4. So program should return 4.

I got this task in a competitive exam last week, when I used this code it has passed only 50% test cases. It failed for some hidden test cases saying wrong output, and some test cases saying time out.	

What is the issue with my code?

**Update:**
Modified my code little bit. And added a sample example.

</details>


# 答案1
**得分**: 1

嵌套循环意味着性能为 _O(n<sup>2</sup>)_。你需要重新思考算法。

下面是一个 _O(n)_ 的解决方案，我会通过示例来展示。编写代码仍然是你的挑战。

我们需要一种方法来知道特定索引之前的值的总和。有了这个，我们可以计算 `sumRange(i, j) = sumBefore(j) - sumBefore(i)`。

因为我们正在寻找 `sumRange(i, j) = k`，我们需要检查是否有 `sumBefore(i) = sumBefore(j) - k`。如果有，我们就有一个候选的范围，其 `size = j - i`。

因此，遍历这些值并计算累积和。构建一个从累积和到导致该累积和的值的 `Map`。

假设数组是 `[1, 6, 5, 3, 2, 8, 4, 2, 7, 1]`，且 `k = 13`：

```lang-java
索引:          0   1   2   3   4   5   6   7   8   9
值:            1   6   5   3   2   8   4   2   7   1
累积和:     0   1   7  12  15  17  25  29  31  38  39   sumBefore
            ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓
之后索引: 0   1   2   3   4   5   6   7   8   9  10   index

添加虚拟的 0 → 0 映射只是为了简化代码逻辑。

当你进行迭代时，你拥有到目前为止（包括）的累积和，即 sumBefore(i + 1)，因此查看是否有一个范围，即 sumBefore(x) = sumBefore(i + 1) - k = accSum - k，因此在映射中查找 accSum - k，如果找到，该值是 x，意味着我们有一个候选的范围 x, i+1。

希望上述内容都讲得清楚。

更新

问题已更改为寻找和 <= k，而不仅仅是寻找和恰好等于 k。

通过上面的逻辑，可以很容易地通过将 Map 更改为 TreeMap，或者更具体地说是 NavigableMap，并将 get() 调用替换为 ceilingEntry() 调用来实现：

返回与大于等于给定键的最小键关联的键值映射；如果没有这样的键，则返回 null。

如果返回的键（和）大于参数，结果是小于 k 的子数组和。

Index:          0   1   2   3   4   5   6   7   8   9
Value:          1   6   5   3   2   8   4   2   7   1
accSum:     0   1   7  12  15  17  25  29  31  38  39   sumBefore
↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓
indexAfter: 0   1   2   3   4   5   6   7   8   9  10   index