时间戳

首页 > 解决方案 > 查找最大索引 j 的有效算法，使得从索引 i 到 j 的总和小于 k

arrays - 查找最大索引 j 的有效算法，使得从索引 i 到 j 的总和小于 k

问题描述

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

标签： arraysalgorithm

解决方案

先前的答案不正确，但我会留下它，因为它已被接受并有评论。
有一种O(n)时间、O(1)空间滑动窗口（或“两个指针”）的方法。下面的代码是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的前缀总和使用二进制搜索（请注意前缀总和是 1 索引的事实）。由此产生的复杂性将是时间和空间。pref[i + 1] ... pref[N]iO(N logN)O(N)

推荐阅读