我是双指针模式的新手，尤其是滑动窗口技术。我在leetcode-Count Nice子数组上遇到了这个问题。我见过很多将数组更改为0和1的解决方案，然后找到总和为K的子数组的数量就变成了一个完全不同的问题。但是，如何在不操纵输入数组的情况下应用滑动窗口技术呢？
我发现了一种解决方案；真的"；简单的解释，但什么证据可以证明，取下限和上限的差会给出正确的答案？下界表示什么？我们非常感谢对直觉的任何帮助或解释。解决方案在下面，解决方案的链接在这里：讨论页面的链接
附言：我试过联系帖子的作者，但没有收到任何建议
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;
}
在我的回答中，我提到了几个引理。我已经用简单的方式证明了前三个，并且只为后两个提供了视觉表示。我这样做是为了避免复杂性，也是因为它们看起来微不足道。
我已经更改了算法中使用的变量名。在整个讨论过程中，我假设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。
Lemma
设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更改为下一个奇数，它成为新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几率的思想反映在算法中。
L4: Each index in [l,f] acts an starting point for a sub-array having k odds in [l,i].
这里k＝2。所有可用作具有k赔率的子阵列的起始点的索引都用CCD_ 6标记。
* * *
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赔率的子阵列的终点的索引都用CCD_ 7标记。
' ' '
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.中
对比
在原始算法中，下界总是比实际下界小1。因此，它被初始化为-1，我们设置lowBound = indexOfLeftMostOddInWin，而在更新的算法中，我们设置了l = f+1。这也意味着我们不需要在答案中添加额外的1。