참고
문제해설
NOTE
•
입력 값 ⇒ 정수 배열과 정수 값
•
출력 값 ⇒ 정수 배열에서 주어진 정수 값을 만들 수 있는 최소길이를 반환한다. 만약 없다면 0을 반환
문제 로직고민
NOTE
•
길이 1부터 배열의 길이 n만큼 길이의 모든 경우를 구한다.
◦
이 경우 단순히 반복분 2개를 사용하면 시간복잡도가 높게 나오므로 슬라이딩 윈도우 기법을 사용한다
◦
그런데 이렇게 하면 최악의 경우 배열길이 전부를 사용해서 해결해야하는 경우 N^2의 시간복잡도가 나온다.
•
투포인터 방식을 응용하자
◦
이전 문제에서 활용했던 투포인터 문제를 응용하기로 했다.
◦
left, right 2개의 포인터를 두고 다음의 조건으로 순환한다.
◦
left - right 범위의 배열값이 조건보다 작다 ⇒ right를 늘린다.
◦
left - right 범위의 배열이 조건보다 크다 ⇒ 기존보다 길이가 짧은경우 갱신하고, left를 늘린다.
작성코드
NOTE
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = nums.length+1;
int left = 0;
int sum = 0;
for(int right = 0 ; right<nums.length ; right++){
sum+=nums[right];
while(sum>=target){
result = Math.min(result,right-left+1);
sum-=nums[left++];
}
}
return result==nums.length + 1 ? 0 : result;
}
}
Java
복사
정답코드
NOTE
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int count=Integer.MAX_VALUE;
int start=0,end=0;
int sum=0;
for(int i=0; i<nums.length; i++){
sum+=nums[i];
if(sum>=target){
end=i;
count=Math.min(count, end-start+1);
}
while(sum > target){
sum-=nums[start++];
if(sum >= target)
count=Math.min(count, end-start+1);
}
}
System.gc();
return count==Integer.MAX_VALUE?0:count;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•