计算 Nice 子数组 - 了解滑动 window 技术而不是前缀和

Question

我是双指针模式的新手，尤其是 Sliding Window technique. I encountered this problem on leetcode - Count Nice Subarrays。我见过许多将数组更改为 0 和 1 的解决方案，然后找到总和为 K 的子数组的数量就变成了一个完全不同的问题。但是如何在不操纵输入数组的情况下应用滑动 Window 技术？

我找到了一个具有“真正”简短解释的解决方案，但是有什么证据表明采用下限和上限的差异将给出正确的答案？ lowBound 表示什么？非常感谢对所用直觉的任何帮助或解释。解决方案如下，解决方案的 link 在这里：Link to Discussion page

PS：我尝试联系 post 的作者，但没有收到任何建议

  public int numberOfSubarrays(int[] nums, int k) {
    int ans = 0, indexOfLeftMostOddInWin = 0, lowBound = -1;
    for (int num : nums) {
        k -= num % 2;
        if (nums[indexOfLeftMostOddInWin] % 2 == 0) // move to the index of first odd.
            ++indexOfLeftMostOddInWin;
        if (k < 0) { // more than k odds in window, need to shrink from low bound.
            lowBound = indexOfLeftMostOddInWin; // update the low bound value.
        }
        while (k < 0) {
            k += nums[++indexOfLeftMostOddInWin] % 2; // move to the index of next odd.
        }
        if (k == 0) { // accumulated k odd numbers in window.
            ans += indexOfLeftMostOddInWin - lowBound; // update result.
        }
    }
    return ans;
}

Answer 1

在我的回答中，我提到了几个引理。我已经以简单的方式证明了前三个，并且只提供了最后两个的可视化表示。我这样做是为了避免复杂性，也因为它们看起来微不足道。

我更改了算法中使用的变量名。在整个讨论过程中，我假设 k=2.

 N: numbers array
 n: an element of N
 l: lower boundary
 f: index of the first odd number after l
 c: count of the number of sub-arrays having k odds

 1: c = 0
 2: f = 0
 3: l = 0
 4: 
 5: for n in N
 6:     k -= n % 2
 7:     if N[f] % 2 == 0: f++ 
 8:     if k < 0: l = f+1               // Found kth+1 odd starting from l, hence update l    
 9:     while k < 0: k += N[++f] % 2  // Set f to the index of next 1st odd after l        
10:     if k == 0: c += (f-l+1)    
11:
12: return c

注意： 我已将 l 的初始值更改为 0。这对答案没有任何影响，因为我有在第 10 步中向 c 添加了一个额外的 1。

引理

设r为从l开始的第k个奇数的索引。

L1: We only decrement k by 1 when we encounter an odd n.

这很容易从 步骤 6 证明。我们在每次迭代中将 k 减少 n%2。

L2: f always points to the index of 1st odd after l.

最初，l=0。我们在第 7 步的每次迭代中更新 f 以确保 f 指向从 l.

开始的第一个奇数索引

在更新时，步骤 8-9 确保无论何时我们将 l 更改为 f+1。我们还将 f 更改为下一个奇数，它成为 new l.

的第一个奇数

因此，在每次迭代中都保留了 f 的作用。

L3: There can never be more than k odds in [l,i].

最初，l=0。当我们遇到新的奇数时，我们继续递减 k。

当第 k+1 个奇数到达索引 i 时，k 变为 -1。从第 8 步和 L2，然后我们将 l 更新为 f+1。

因此，现在 [l, i] 中有 k 个赔率。我们再次将步骤 9 中的 k 更新为 0，以确保 [l, i] 中的 k odds 的想法反映在算法中。

L4: Each index in [l,f] acts an starting point for a sub-array having k odds in [l,i].

这里k=2。所有可以作为具有k-odds的子数组起点的索引都用*.

标记

* * *
l   f   r   i
E E O E O E E

L5: Each index in [r,i] acts an ending point for a sub-array having k odds in [l,i].

这里k=2。所有可以作为具有k-odds的子数组终点的索引都用'.

标记

        ' ' '
l   f   r   i
E E O E O E E

讨论

一开始，我们寻找第一个奇数。当我们发现时，我们继续递减 k 新奇数。令 k=2.

l   f   i
E E O E O

这里在第i次迭代中，当k的值为0时，我们找到了k个几率。现在，使用 L4，我们知道 [l, f] 中的所有索引都是具有 k 个几率的子数组的起点。此类子阵列的数量 = (f-l+1)。这是加到c的数字。

现在，下一个元素可以是偶数或奇数。假设下一个元素是偶数。

l   f   r i
E E O E O E

现在使用L5，我们知道[r, i]中的所有索引都是具有k个几率的子数组的终点。然而，我们已经在最后一步考虑了以索引 (i-1) 作为其终点的子数组。因此，我们只需要考虑以 i 为终点的子数组，也就是 (f-l+1)。我们又再次将此数字添加到 c.

现在，假设这之后的下一个元素是奇数。

      l f   i
E E O E O E O

这里所有的变量都是按照L3更新的，保证新的子数组里面有k个奇数。 k的值再次为0，我们将这些新找到的子数组添加到c.

比较

在原算法中，lowBound总是比实际的下边界小1。因此，它用 -1 初始化，我们设置 lowBound = indexOfLeftMostOddInWin，而在更新的算法中，我们设置 l = f+1。这也意味着我们不需要在答案中添加额外的 1。

计算 Nice 子数组 - 了解滑动 window 技术而不是前缀和

Count Nice Subarrays - Understanding sliding window technique and not prefix sum

arrays

algorithm

pointers

data-structures

sliding-window

引理

讨论

比较