LeetCode Top Interview 150 - 209. Minimum Size Subarray Sum

🤔 문제 이해

이번 문제를 이해하기 바로 직전에 Slide Window알고리즘을 정리하고 왔기때문에 바로 알 수있었다. (알고리즘의 문제 예시로 정리한 문제)

주어진 양수로 이루어진 배열에서 연속된 부분 수열 중 원하는 합 이상을 만족하는 최소 길이의 부분 수열을 찾는 문제

 

 

🤔 EX

data example 1
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

data example 2
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

data example 3
Input: target = 15, nums = [1,2,3,4,5]
Output: 5

 

🤔 의사 코드 

minLength 길이를 제일 크게 선언
let s = 0인덱스 시작인 0을 변수에 저장
계산 누적할 변수를 선언 하며 0저장

for(nums의 길이만큼 돌아감: let i=0;i<nums.length;i++){
누적변수에 돌아가면서저장 
	while(누적변수>= target){
		math.min으로 minLength길이 구해줌 [i - s +1]
        누적변수 -= nums[s]
        s++
	}
    return minLength===Infinity ? 0 : minLength
}

정리
함수는 변수 minLength을 무한대로 초기화하고, 포인터 s를 0으로 설정합니다. 또한 result 변수를 0으로 초기화합니다.
함수는 배열의 각 요소에 대해 반복문을 실행합니다. 반복문 내에서는 result에 현재 요소를 더하고, result가 target 이상이 될 때까지 s를 증가시키며 result에서 s번째 요소를 뺍니다.
이 과정을 통해 result가 target 이상이 되면, minLength를 현재 부분 배열의 길이(i - s + 1)와 비교하여 더 작은 값으로 업데이트합니다.
함수는 전체 배열을 순회할 때까지 2단계를 반복합니다.
마지막으로, 함수는 minLength가 무한대인 경우 0을 반환하고, 그렇지 않으면 minLength를 반환합니다.

🤔 해결한 코드 :  O(n)

var minSubArrayLen = function(target, nums) {
    let minLength = Infinity
    let s = 0
    let result = 0

    for(let i=0;i<nums.length;i++){
        result+=nums[i]
        
        while(result>= target){
            minLength = Math.min(minLength,i-s+1)
            result -= nums[s]
            s++
        }
    }
    return minLength === Infinity ? 0:minLength
};