Leetcode209.MinimumSizeSubarraySum

문제

• 209. Minimum Size Subarray Sum

• 양수 nums (int array), 양수 target 이 주어짐

• nums 부분배열의 합이 크거나 같은 subarray (연속적) min length 구하기

풀이 (window)

• window 생각하고 포인터를 이동시키면서 subarray length 구하면 됨
• 자세한 설명은 아래 주석

source

     /**
     *  1. 문제
     *  - 양수 nums 주어짐
     *  - 양수 target 도 주어짐
     *  - 부분배열의 합이 크거나 같은 minimal length 였네.
     *  - 연속된 sequence 맞네
     *      - 여러개가 나올 수 있음. 최소 length 를 구해야함
     *  - 답이 없으면 0 을 return
     *  - 시간복잡도를 O(n) 이 아니라 O(nlog(n)) 으로 풀어야 함
     *
     *  Constraints:
     * 1 <= target <= 10 9승
     * 1 <= nums.length <= 10 5승
     * 1 <= nums[i] <= 10 4승
     *
     *
     *  2. 풀이
     *  2.1 window
     *  - start, end 동시에 0 부터 시작
     *  - 순회할 때는 end 를 늘리고, target 이 넘어가면 start 를 늘리는거였나
     *  - 음 잘못푼거 같은데 -> 최소 length 를 구해야함
     *  - nums 순회하면서 시작점을 한칸씩 이동해서 window 를 구해야하나?
     *  - nums element 는 양수니까 window 가 target 넘어서는 순간 더 이상 구할 필요 없음
     *  - 시간복잡도 O(n 제곱)
     *  - 문제를 잘못이해했네. subarray (연속적인 sequence) target 보다 크거나 같은 것을 구하는 것
     *
     *  처음에는 for loop 2번 돌렸음
     *  개선해서 for loop 1번만 돌려도 됨
     *  target <= sum 이면 start++ 하면서 pointer 이동
     */

    fun minSubArrayLen2(target: Int, nums: IntArray): Int {
        var minSubArrayLen = Integer.MAX_VALUE
        for (i in 0 until nums.size) {
            var sum = 0
            var start = i
            var end = i

            while (start <= end && end < nums.size) {
                sum += nums[end]
                if (sum >= target) {
                    minSubArrayLen = Math.min(end - start + 1, minSubArrayLen)
                    break
                } else if (sum < target) {
                    end++
                }
            }
        }
        return if (minSubArrayLen == Integer.MAX_VALUE) 0 else minSubArrayLen
    }

    fun minSubArrayLen(target: Int, nums: IntArray): Int {
        var minSubArrayLen = Integer.MAX_VALUE
        var sum = 0
        var start = 0
        var end = 0

        while (start <= end && end < nums.size) {
            sum += nums[end]
            if (sum >= target) {
                minSubArrayLen = Math.min(end - start + 1, minSubArrayLen)
                sum -= nums[start]
                sum -= nums[end]
                start++
            } else if (sum < target) {
                end++
            }
        }
        return if (minSubArrayLen == Integer.MAX_VALUE) 0 else minSubArrayLen
    }