사용언어 : JAVA
k
를 만족하는 배열의 시작과 끝 idx를 answerStart
와 answerEnd
저장한다.maxSize
에 부분 수열의 길이를 저장하고, 부분 수열의 합이 k
를 만족하는 배열의 길이를 비교해 작을 경우 answerStart
와 answerEnd
를 바꾸어주기. class Solution {
public int[] solution(int[] sequence, int k) {
int[] cal = new int[sequence.length];
cal[0] = sequence[0];
// 누적합을 저장
for(int i = 1; i < sequence.length; i++) {
cal[i] = cal[i-1] + sequence[i];
}
int answerEnd = 0;
int answerStart = 0;
int maxSize = sequence.length;
for(int i = 0; i < sequence.length; i++) {
if (maxSize == 1) {
break;
}
if(cal[i] < k) continue;
if(cal[i] == k){
if(maxSize > i){
answerEnd = i;
answerStart = -1;
maxSize = i+1;
}
continue;
}
for(int j = i-1; j >= answerStart; j--){
if(cal[i] - cal[j] > k || i-j >= maxSize ){
break;
}
if(cal[i] - cal[j] == k && i-j < maxSize) {
answerEnd = i;
answerStart = j;
maxSize = i-j;
break;
}
}
}
int[] answer = {answerStart+1, answerEnd};
return answer;
}
}
투포인터 알고리즘을 활용
투포인터 알고리즘이란?
리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
while문을 사용해 sum
(부분 수열의 합)을 구합니다.
만약 sum
이 k
일 경우 배열의 길이을 구하고 left
, right
와 비교해 arraySize
가 작을경우 left
와 right
를 갱신 시켜줍니다.
마지막으로 l을 옮기면서 sum에서 sequence[l]을 빼줍니다.
class Solution {
public int[] solution(int[] sequence, int k) {
int n = sequence.length;
int left = 0;
int right = n;
int sum = 0;
for(int l = 0, r = 0; l < n; l++){
while(r < n && sum < k) {
sum+= sequence[r++];
}
if(sum == k) {
int arraySize = r - l -1;
if((right-left) > arraySize ) {
left = l;
right = r - 1;
}
}
sum -= sequence[l];
}
int[] answer = {left, right};
return answer;
}
}