2

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

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

思考过程

我的思考过程如下：

  • 第 1 步：给定原始数组 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]满足上述属性的值 where 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);

我的算法现在奏效了。

我的问题

  1. 我真的不明白这里发生了什么。为什么我的初始代码不起作用，为什么当我更改前缀和数组时它起作用？

  2. 如果我想使用原始前缀和数组（即不以 0 开头的数组），我需要对我的算法进行哪些更改

4

1 回答 1

0

你在逻辑上的缺陷在于

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

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

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

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

于 2020-06-23T04:04:38.547 回答