문제
양의 정수 숫자와 양의 정수 대상의 배열이 주어지면, 합이 대상보다 크거나 같은 연속 하위 배열[numsl, numsl+1, ..., numsr-1, numsr]의 최소 길이를 반환합니다. 이러한 하위 배열이 없으면 0을 반환하십시오.
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
https://leetcode.com/problems/minimum-size-subarray-sum/
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
풀이
자바입니다.
- 슬라이딩 윈도우를 사용했습니다.
- min 최소길이입니다. left 왼쪽 창문, right 오른쪽 창문 입니다.
- 배열을 반복해서 sum 에 값을 더합니다.
- sum 이 target 보다 크거나 같으면 while문을 실행한다.
- sum-=nums[left++] 은 왼쪽창문을 닫는 것입니다.
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int min = Integer.MAX_VALUE;
int left = 0;
int sum = 0;
for(int right = 0 ; right<nums.length ; right++){
sum+=nums[right];
while(sum>=target){
min = Math.min(min,right-left+1);
sum-=nums[left++];
}
}
return min==Integer.MAX_VALUE?0:min;
}
}문제를 잘못 읽었습니다. '연속되는 배열'을 무시하고 문제를 풀다 시간을 많이 잡아먹었습니다.
문제를 차근차근 읽어야 합니다. 제발.
https://leetcode.com/problems/minimum-size-subarray-sum/discuss/1769644/JAVA-99-O(N)-solution-Sliding-window-(With-visualization)
슬라이딩 윈도우 알고리즘을 시각화한 풀이입니다.
