描述

在由若干?0?和?1?組成的數組?A?中，有多少個和為?S?的非空子數組

樣例 1:

輸入：A = [1,0,1,0,1], S = 2
輸出：4
解釋：
如下面黑體所示，有 4 個滿足題目要求的子數組：
[1,0,1]
[1,0,1]
[1,0,1,0]
[0,1,0,1]

樣例 2:

輸入：A = [0,0,0,0,0,0,1,0,0,0], S = 0
輸出：27
解釋：
和為 S 的子數組有 27 個

思路1 采用同向雙指針法 通過暴力雙指針枚舉所有起點 + 滑動右指針

每輪固定左指針 left，右指針從 left 向右滑動； 每次累加和，如果等于 S，就記錄這個子數組； 關鍵點是從每個 left 出發，向右滑，不能隨便跳過任何一個組合

代碼1:

public class Solution {

? ? public int numSubarraysWithSum(int[] A, int S) {

? ? ? ? int n=A.length;

? ? ? ? int count=0;

? ? ? ? for(int left = 0; left < n; left++)//同向雙指針法計算是否為目前值S

? ? ? ? {

? ? ? ? ? ? int accumulatedNum = 0;

? ? ? ? ? ? for (int right = left; right < n; right++) {

? ? ? ? ? ? ? ? accumulatedNum += A[right];

? ? ? ? ? ? ? ? if (accumulatedNum == S) {

? ? ? ? ? ? ? ? ? ? count++;

? ? ? ? ? ? ? ? } else if (accumulatedNum > S) {

? ? ? ? ? ? ? ? ? ? break; // 再滑動右指針沒意義了

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? ? ?

? ? ? ? }

? ? ? ? return count;

? ? }

}

思路2 前綴和 + 哈希表

每輪固定左指針 left，右指針從 left 向右滑動； 每次累加和，如果等于 S，就記錄這個子數組； 關鍵點是從每個 left 出發，向右滑，不能隨便跳過任何一個組合

任意一個子數組 [i..j] 的和 = prefixSum[j] - prefixSum[i-1] 若要求 sum[i..j] = S，則等價于： prefixSum[j] - prefixSum[i-1] == S → prefixSum[i-1] == prefixSum[j] - S

prefixMap 來記錄前綴和出現的次數，作用是：

鍵（Key）	值（Value）
某個前綴和 x	這個前綴和 x 出現過多少次

prefixMap.put(0, 1);?

前綴和為 0 出現了 1 次（這是初始化）

它允許我們從下標 0 開始的子數組也能被統計進來

accumulatedNum 當前前綴和，也就是從 A[0] 到 A[i] 的累加值

count 當前找到的子數組個數，最終返回這個值

步驟 1：累加前綴和?

accumulatedNum += A[i]; // 累加前綴和 將當前元素 A[i] 累加到 accumulatedNum 中； accumulatedNum 代表前綴和 prefixSum[i]

每次比較都是當前前綴和-s 當有

既等式

prefixSum[j] - prefixSum[i-1] == S
→ prefixSum[i-1] == prefixSum[j] - S
→ accumulatedNum - S

是我們想找的值 意思為在前面的位置出現過這樣一個前綴和，
這樣從那個位置之后到我當前位置，就剛好是一個和為 S 的子數組

prefixMap.get(accumulatedNum - S)之前有多少個位置，它們的前綴和等于 accumulatedNum - S

每一個都可以作為「合法子數組的起點」，從那個點到當前 i 的子數組和為 S。
所以：prefixMap.get(accumulatedNum - S) 就是當前命中的合法子數組個數

prefixMap.put(accumulatedNum, prefixMap.getOrDefault(accumulatedNum, 0) + 1);
把當前的前綴和 accumulatedNum 的出現次數 +1

因為我們要統計「從前面某個位置 i 到當前位置 j 的和為 S 的子數組數量」。

每一個前綴和，都可能為后面提供組合，所以我們必須記錄它出現的次數

import java.util.*;

public class Solution {
? ? public int numSubarraysWithSum(int[] A, int S) {
? ? ? ? int accumulatedNum = 0; // 當前的前綴和
? ? ? ? int count = 0;

? ? ? ? Map<Integer, Integer> prefixMap = new HashMap<>();
? ? ? ? prefixMap.put(0, 1); // 初始化：前綴和為 0 出現了 1 次

? ? ? ? for (int i = 0; i < A.length; i++) {
? ? ? ? ? ? accumulatedNum += A[i]; // 累加當前前綴和

? ? ? ? ? ? // 如果之前出現過 accumulatedNum - S，就說明找到了滿足條件的子數組
? ? ? ? ? ? if (prefixMap.containsKey(accumulatedNum - S)) {
? ? ? ? ? ? ? ? count += prefixMap.get(accumulatedNum - S);
? ? ? ? ? ? }

? ? ? ? ? ? // 更新當前前綴和出現次數
? ? ? ? ? ? prefixMap.put(accumulatedNum, prefixMap.getOrDefault(accumulatedNum, 0) + 1);
? ? ? ? }

? ? ? ? return count;
? ? }
}? ?

一個疑問點是如果不寫

那么就會漏掉那些從 index = 0 開始就滿足和為 S 的子數組

例 A = [1, 0, 1], S = 2

有 prefixMap.put(0, 1) 的時候：

i	A[i]	accumulatedNum	accumulatedNum - S	prefixMap命中	count
0	1	1	-1	?	0
1	0	1	-1	?	0
2	1	2	0	?	1

最終結果：?找到了子數組 [0, 1, 2]，和為 2。

當prefixMap.put(0, 1)沒有的時候?

當前累計為 2 的時候，你想找的前綴和是 0，但 prefixMap 里沒有

prefixMap.getOrDefault(accumulatedNum, 0) 會取下標為0的值 因為沒有放入1 則

這段合法子數組 [1, 0, 1] 就不會被統計 即錯誤結果?最終結果是:count=0

推薦剛開始學習使用雙指針法 進階使用前綴和 + 哈希表