題目

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

示例：輸入：A = [1,0,1,0,1], S = 2 輸出：4

解釋： 如下面黑體所示，有 4 個滿足題目要求的子陣列：

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

提示：A.length <= 30000

0 <= S <= A.length

A[i] 為 0 或 1

解題思路分析

1、字首和；時間複雜度O(n)，空間複雜度O(n)

func numSubarraysWithSum(A []int, S int) int {	m := make(map[int]int)	res := 0	sum := 0	for i := 0; i < len(A); i++ {		sum = sum + A[i]		if sum == S {			res++		}		res = res + m[sum-S]		m[sum]++	}	return res}

2、字首和；時間複雜度O(n)，空間複雜度O(n)

func numSubarraysWithSum(A []int, S int) int {	m := make(map[int]int)	res := 0	sum := 0	m[0] = 1	for i := 0; i < len(A); i++ {		sum = sum + A[i]		res = res + m[sum-S]		m[sum]++	}	return res}

3、雙指標；時間複雜度O(n^2)，空間複雜度O(1)

func numSubarraysWithSum(A []int, S int) int {	res := 0	sum := 0	left := 0	for i := 0; i < len(A); i++ {		sum = sum + A[i]		if sum > S { // 左指標右移			for left < i && sum != S {				sum = sum - A[left]				left++			}		}		if S == sum {			tempSum := sum			j := left			for j <= i && tempSum == S { // 以該節點為結尾有多少個子陣列sum==S				res++				tempSum = tempSum - A[j]				j++			}		}	}	return res}

總結

Medium題目，使用字首和解決