需要帮助了解二进制搜索如何在前缀和数组上工作

Question

我正在解决问题 Minimum Size Subarray Sum。我正在尝试通过对前缀和数组使用二进制搜索来解决它，该前缀和数组解决了 n*log(n) 复杂度的问题。

我设法让它工作，但我不明白为什么我的解决方案有效。

思考过程

我的思路是这样的：

第一步：给定原始数组nums，首先我创建一个前缀和数组如下：

第 2 步：然后我应用以下逻辑：

  /*
      need to find min r-l+1 such that
      prefix[r] - prefix[l-1] >= k
      prefix[r] - k >= prefix[l-1]
      tgt >= prefix[l-1]
  */

第 3 步：我遍历 prefix[] 数组 - 这表示 prefix[r]。由于 nums 具有所有正值，因此 prefix 数组始终递增 - 即它已排序。然后，我在 prefix 上使用二进制搜索来查找满足上述属性的 prefix[l-1] 值，其中 tgt >= prefix[l-1].

代码

我的代码如下：

public int minSubArrayLen(int s, int[] nums) {
    int[] prefix = new int[nums.length];
    int res = Integer.MAX_VALUE;

    for(int i=0; i<nums.length; i++) {
        if(i==0)
            prefix[i] = nums[i];
        else
            prefix[i] = nums[i] + prefix[i-1];
    }

    for(int i = 0; i<prefix.length; i++) {
        int tgt = prefix[i] - s;
        int index = binarySearch(0, i, tgt, prefix);
        if(index >= 0) {
            res = Math.min(res, i-index+1);
        }
    }
    return res == Integer.MAX_VALUE? 0 : res;
}

private int binarySearch(int l, int r, int tgt, int[] a) {
    int res = -1;
    while(l<=r) {
        int mid = l + (r-l)/2;
        if(tgt >= a[mid]) {
            res = mid;
            l = mid+1;
        } else {
            r = mid-1;
        }
    }
    return res;
}

这不起作用。所以我对前缀数组进行了以下更改，使其以 0:

开头

int[] prefix = new int[nums.length+1];
for(int i=0; i<nums.length; i++)
    prefix[i+1] = nums[i] + prefix[i];

并且我编辑了子数组的计算方式以解决这些变化：

res = Math.min(res, i-index);

我的算法现在起作用了。

我的问题

我真的不明白这里发生了什么。为什么我的初始代码不起作用，为什么当我更改前缀和数组时却起作用？
如果我想使用原来的前缀和数组（即不以0开头的那个），我的算法需要做哪些改动

Answer 1

你的逻辑错误在于行

res = Math.min(res, i-index+1);

因为对于前缀数组，连续2个元素的差只代表原数组的ONE长度段。以此类推，计算原始段长度的公式总是i-index，而不是i-index+1。

然而，如果你只修复那一行，还有另一种极端情况：如果原始数组中段的有效总和从头开始怎么办？您将在前缀数组中减去什么？此后，在前缀数组的开头添加一个 0 元素将解决此问题，因为任何其他元素现在都有一个 0 元素来进行减法。

希望这能解释你的修复是如何真正起作用的。

需要帮助了解二进制搜索如何在前缀和数组上工作

Need help understanding how Binary Search works on prefix sum arrays

arrays

algorithm

binary-search

data-structures

prefix-sum