求最大指数j的有效算法，使得指数i到j的和小于k

Question

给我一个大小为n的正整数数组。对于数组中的每个索引I，我想找到最大的索引j，使得从索引I到j的数组元素之和小于或等于某个整数K。我只能用蛮力O（n^2）的方式来思考。我想知道是否有更有效的方法？

Answer 1

前面的答案是错误的，但我会留下它，因为它被接受，并有一个评论
有一种O（n）time，O（1）space滑动窗口（或“双指针”）方法。下面的代码是用Java编写的：

public static int[] rightBoundSums(int[] arr, long K) {
    final int N = arr.length;

    int[] ans = new int[N]; // the result

    int r = 0; // the right index of the window
    long sum = 0; // current sum
    for (int l = 0; l < N; l++) {
        // invariant: r is the first such index that 
        // sum(l, r - 1) > K, or N, if the end of the array was reached
        while (r < N && sum <= K) {
            sum += arr[r++];
        }

        if (arr[l] > K) {
            ans[l] = -1; // if the i-th element itself is larger, than K, there is no such j
        } else {
            ans[l] = (r == N) ? N - 1 : r - 2;
        }

        sum -= arr[l];
    }

    return ans;
}

计算前缀和pref[0]=0，pref[i]=pref[i-1]arr[i-1]。由于arr的值是正的，因此可以使用前缀和arr[i]k对每个pref[i 1]... pref[N]的前缀和进行二进制搜索（请注意前缀和是1-index的事实）。结果的复杂度将是O（N logN）time和O（N）space。