๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”ํ…Œ

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
};