930. Binary Subarrays With Sum - Medium

前往題目

想法

• Sliding window
• 但是全0的case不知道該怎解

思路

這題最重要的是找出<= goal以及<= goal - 1總共有幾個valid window相減，如此一來就能找出== goal的有幾個window了

1. helper方法回傳goal減去goal - 1的結果
2. helper就是標準的sliding window程式

Code

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        return helper(nums, goal) - helper(nums, goal - 1);
    }

    private int helper(int[] nums, int goal) {
        // Base case
        if (goal < 0) return 0;

        int res = 0;
        int l = 0;
        int curSum = 0;

        for (int r = 0; r < nums.length; ++r) {
            // update current sum
            curSum += nums[r];

            // Make sure valid
            while (l <= r && curSum > goal) {
                curSum -= nums[l];
                ++l;
            }

            // Count all the windows
            res += r - l + 1;
        }
        return res;
    }
}