[LeetCode][Kotlin] 930. Binary Subarrays With Sum

930. Binary Subarrays With Sum

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

 

A subarray is a contiguous part of the array.

이진 배열 nums와 정수 goal이 주어지면, sum goal을 사용하여 비어 있지 않은 부분 배열의 개수를 반환합니다. 

부분 배열은 배열의 연속된 부분입니다.

 

Example 1:

Input: nums = [1,0,1,0,1], goal = 2

Output: 4

Explanation: The 4 subarrays are bolded and underlined below:

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

 

Example 2:

Input: nums = [0,0,0,0,0], goal = 0

Output: 15

 

Constraints:

• 1 <= nums.length <= 3 * 10^4
• nums[i] is either 0 or 1.
• 0 <= goal <= nums.length

---

코드

• Example 1

r	helper(2) 부분 배열	helper(1) 부분 배열
0	[1]	[1]
1	[1], [1, 0]	[1], [1, 0]
2	[1], [1, 0], [1, 0, 1]	[0], [0, 1]
3	[1], [1, 0], [1, 0, 1], [1, 0, 1, 0]	[0], [0, 1], [0, 1, 0]
4	[0], [0, 1], [0, 1, 0], [0, 1, 0, 1]	[0], [0, 1]

class Solution {
    fun numSubarraysWithSum(nums: IntArray, goal: Int): Int {
        fun helper(x: Int): Int {
            if (x < 0) return 0

            var answer = 0
            var sum = 0
            var l = 0

            for (r in nums.indices) {
                sum += nums[r]

                while (sum > x) {
                    sum -= nums[l]
                    l++
                }

                answer += (r - l + 1)
            }

            return answer
        }

        return helper(goal) - helper(goal - 1)
    }
}