문제
Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
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
Constraints:
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).
주어진 target 값과 배열의 합이 같거나 큰 subarray를 만들 수 있다면 그 배열의 최소 길이, 없다면 0을 반환한다.
O(n)의 해를 찾을 수 있다면, O(n long(n))를 갖는 해도 찾아보자.
풀이 1
문제가 요구하는 그대로 Greedy 구현을 해보자.
1. 보조 배열의 길이를 1부터 배열의 최대 길이까지 하나씩 늘린다.
2. index 0 부터 보조 배열의 길이만큼의 합을 구한다.
3. 합이 target과 같거나 크면 반환한다.
4. 반환하지 못했다면 0을 반환한다.
결과 1
class Solution {
public int minSubArrayLen(int target, int[] nums) {
for (int length = 1; length <= nums.length; length++) {
for (int i = 0; i <= nums.length - length; i++) {
int sum = 0;
for (int j = i; j < i + length; j++) {
sum += nums[j];
}
if (sum >= target) return length;
}
}
return 0;
}
}
배열이 길이가 아주 큰 경우 Time out이 발생하였다.
풀이 2
시간축을 위해 다른 방식으로 풀이 해야한다.
연속된 배열인 점을 고려하여 two pointer 알고리즘을 적용한다.
1. start, end는 0부터 시작한다.
2. end 부터 index를 증가시킨다. 이때, num[end] 값을 sum에 더한다.
3. sum이 target보다 같거나 크면 start의 index를 증가시킨다. 이때, num[start] 값을 sum에서 뺀다.
3-1. sum이 target보다 같거나 크면 해당 길이 (end - start) 를 저장한다.
4. end 가 배열의 끝에 다다르면 종료한다.
결과 2
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int start = 0;
int end = 0;
int result = Integer.MAX_VALUE;
while (end < nums.length) {
sum += nums[end++];
while (sum >= target) {
result = Math.min(result, end - start);
sum -= nums[start++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
