[leetcode/lintcode 題解] 阿裡算法面試真題詳解：和相同的二進制子數組

描述

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

• A.length <= 30000
• 0 <= S <= A.length
• A[i] 為 0 或 1

線上評測位址：

領扣題庫官網

樣例1
Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1]
[1,0,1]
[1,0,1,0]
[0,1,0,1]           

樣例2
Input: A = [0,0,0,0,0,0,1,0,0,0], S = 0
Output: 27
Explanation: 
And 27 subarrays for S.           

題解

字首和：定義一個數組sumN+1，si表示數組A中前i個元素之和，然後周遊sum數組，計算si+S(含義：前i個元素之和是si,找和為S的子數組個數)。求si+S的個數

public class Solution {
    /**
     * @param A: an array
     * @param S: the sum
     * @return: the number of non-empty subarrays
     */
    public int numSubarraysWithSum(int[] A, int S) {
        // Write your code here.
        if (A == null || A.length == 0) {
            return 0;
        }
        int prefixSum = 0;
        int res = 0;
        // counts[i] means the number of prefixSum = i
        int[] counts = new int[A.length + 1];
        counts[0] = 1;
        for (int i = 0; i < A.length; i++) {
            prefixSum += A[i];
            if (prefixSum >= S) {
                res += counts[prefixSum - S];
            }
            counts[prefixSum]++;
        }
        return res;
    }
}           

更多題解參考：

九章官網solution