Leetcode 930.BinarySubarraysWithSum

소스코드

문제

• 930.BinarySubarraysWithSum

풀이 (brute-force)

• for loop 2번 돌아서 sum 이 goal 과 일치할 경우 output 을 계산해줬습니다.
• 시간 복잡도 : O(n²) , 공간 복잡도 : 1

    fun numSubarraysWithSum1(nums: IntArray, goal: Int): Int {
        var output = 0
        var sum = 0
        for (i in 0 until nums.size) {
            sum += nums[i]
            if (sum == goal) {
                output++
            }

            for (j in i + 1 until nums.size) {
                sum += nums[j]
                if (sum == goal) {
                    output++
                }
            }
            sum = 0
        }
        return output
    }

풀이 (sliding window)

• 시간 복잡도 : O(n)

   /**
     * 기존 sliding window 를 사용하면 목표에 도달하면 left pointer 를 앞으로 당김.
     * 이럴 경우 원하는 goal 을 못구할 수 있음. 왜냐하면 순회하다 0을 만나면 left 를 이동할 필요 없이 만족하기 때문
     *  -> 여기까진 이해됐음
     *
     * atMost(nums, goal) - atMost(nums, goal - 1) 의미하는 바는
     * goal 보다 작은 부분배열을 제거해서 합이 goal 부분배열을 구하는 것
     *
     * atMost(nums, goal) -> nums 중에 goal 이하의 부분배열의 개수를 전부 구함
     * atMost(nums, goal - 1) -> nums 중에 goal - 1 이하의 부분배열의 개수를 전부 구함
     *
     * atMost(nums, goal) - atMost(nums, goal - 1) -> goal 과 일치하는 부분배열의 개수만 남음
     *
     */
    fun numSubarraysWithSum(nums: IntArray, goal: Int): Int {
        return atMost(nums, goal) - atMost(nums, goal - 1)
    }

    /**
     *  atMost function 은 nums 를 순회하면서 부분배열의 개수를 구함
     *  순회하면서 goal 이 초과하는건 제외시킴. 동시에 pointer 를 앞으로 이동시킴
     *  이동시켜야하는 이유는 window 를 유지한 상태에서 다음것을 구해야하니
     *  
     *  여기서 알아둬야하는 점은 sliding window 의 개념이 포인터를 이동시키면서 원하는 것을 구하는 것이고
     *  원하는 것을 찾았을 때, pointer (tail) 를 움직이는 것.
     *  또 하나의 pointer (head) 는 순회하는 것
     */
    private fun atMost(nums: IntArray, goal: Int): Int {
        var tail = 0   // sliding window 에서 조건을 만족했을 때, 움직이는 것
        var sum = 0
        var result = 0
        for (head in nums.indices) {
            sum += nums[head]

            // goal 을 초과하는건 구하지 않는다. tail 은 head 를 넘어설수 없음.
            while (sum > goal && tail <= head) {
                sum -= nums[tail]   // goal 을 초과하는건 필요없으니 제거한다.
                tail++              // goal 을 초과했으니 pointer 를 앞으로 당긴다.
            }
            // 하위배열 총 개수를 구한다.
            result += head - tail + 1
        }
        return result
    }