๐ค ๋ฌธ์ ์ดํด
์ด๋ฒ ๋ฌธ์ ๋ฅผ ์ดํดํ๊ธฐ ๋ฐ๋ก ์ง์ ์ 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
};
'์ฝํ ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๋ฃ๊ตฌ์กฐ] Linked list - 2 (0) | 2023.08.28 |
---|---|
LeetCode Top Interview 150 - 150. Evaluate Reverse Polish Notation (0) | 2023.08.27 |
LeetCode Top Interview 150 - 3. Longest Substring Without Repeating Characters (0) | 2023.08.26 |
LeetCode Top Interview 150 - 167. Two Sum II - Input Array Is Sorted (0) | 2023.08.25 |
LeetCode Top Interview 150 - 125. Valid Palindrome (0) | 2023.08.25 |