我是兩個指標模式的新手，尤其是滑動視窗技術。我在 leetcode - Count Nice Subarrays 上遇到了這個問題。我見過許多將陣列更改為 0 和 1 的解決方案，然后找到總和為 K 的子陣列的數量就變成了一個完全不同的問題。但是如何在不操作輸入陣列的情況下應用滑動視窗技術？
我找到了一種具有“真正”簡短解釋的解決方案，但是有什么證據表明采用下限和上限的差異會給出正確的答案？低界意味著什么？非常感謝您對所使用的直覺的任何幫助或解釋。解決方案如下，解決方案的鏈接在這里：鏈接到討論頁面
PS：我已經嘗試聯系帖子的作者，但沒有收到任何建議
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;
}
uj5u.com熱心網友回復：
在我的回答中，我提到了一些引理。我以簡單的方式證明了前三個，并且只提供了后兩個的可視化表示。我這樣做是為了避免復雜性，也因為它們看起來微不足道。
我已經更改了演算法中使用的變數名稱。在整個討論中，我假設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。這對答案沒有任何影響，因為我c在步驟 10 中添加了額外的 1。
引理
令r為從 l 開始的第 k 個奇數的索引。
L1: We only decrement k by 1 when we encounter an odd n.
這很容易從步驟 6中得到證明。n%2我們在每次迭代中將k 減少。
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-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
討論
In the start, we look for the first odd. We keep on decrementing k as we find new odd numbers. Let k=2.
l f i
E E O E O
Here at iteration i, when the value of k becomes 0, we have found k odds. Now, using L4, we know all the indices in [l, f] are starting point of sub-arrays having k odds. Number of such sub-arrays = (f-l 1). This is the number added to c.
Now, either the next element can be even or odd. Suppose the next element is even.
l f r i
E E O E O E
Now using L5, we know all the indices in [r, i] are ending point of sub-arrays having k odds. However, we have already considered sub-arrays that have index (i-1) as their ending point in the last step. Thus, we only need to consider sub-arrays that have i as their ending point, which are again (f-l 1). We again again add this number to c.
Now, suppose the next element after this is odd.
l f i
E E O E O E O
這里所有的變數都是按照L3更新的，保證新的子陣列里面有k個幾率。k 的值再次為 0，我們將這些新找到的子陣列添加到 c。
比較
在原始演算法中，lowBound 總是比實際的下邊界小 1。因此，它用 -1 初始化，我們設定lowBound = indexOfLeftMostOddInWin，而在更新的演算法中，我們設定l = f 1。這也意味著我們不需要在答案中添加額外的 1。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/411539.html
標籤：