-
leetcode top interview 150 | Minimum Size Subarray Sum | Sliding windowPS 2023. 8. 29. 10:21
Question
양수로 이루어진 정수배열이 주어졌을때, 하위배열의 합이 target number보다 같거나 클 경우 해당 하위배열의 최소 길이를 반환
target number에 해당하는 경우가 없으면 0 리턴
Accepted Code
import java.util.*; class Solution { public int minSubArrayLen(int target, int[] nums) { int sum = 0; int minLen = Integer.MAX_VALUE; for(int left = 0, right = 0; right < nums.length; right++){ sum += nums[right]; while(sum >= target){ minLen = Math.min(minLen, right - left + 1); sum -= nums[left]; left++; } } return minLen == Integer.MAX_VALUE ? 0 : minLen; } }
Solve
합할 배열의 요소가 연속적으로 구성되어있어야 하므로 고정된 window를 두고 조건에 맞는지 확인하는 슬라이딩 윈도우 기법을 활용해 O(N)의 복잡도로 해결하였다.
left와 right 포인터를 인덱스 0부터 시작하게 하고 right을 증가시켜가며 sum을 구한다.
target 보다 작거나 크게 되면 minLen값을 갱신하고 시작위치에 있는 left를 증가시키면서 윈도우 사이즈를 줄여나간다.
최소 길이를 구해야하기 때문에 target보다 크거나 같은 조건을 만족하면서 지금 길이보다 줄일 수 있는 케이스가 있는지 탐색하는 것이다.
minLen을 MAX_VALUE로 초기화해줬기 때문에 탐색을 해도 초깃값과 동일하면 0을 리턴하고 아니면 갱신한 minLen 값을 리턴한다.
Minimum Size Subarray Sum - LeetCode
Can you solve this real interview question? Minimum Size Subarray Sum - Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarr
leetcode.com
'PS' 카테고리의 다른 글