문제링크

문제링크

문제 설명 & 제한사항

입출력 예 및 설명

풀이

1. 제한사항이 100만이다? 그럼 O(n)안에 끝내자
2. 투포인터 기법으로, left, right 포인터를 가지고 있자
3. left하고 right는 앞으로 한칸씩 움직일 예정이므로, 한발자국씩 나갈때마다 우리는 right - left 값을 알 수 있다.
   3-1 나는 이 부분을 모든 숫자를 더한 배열을 하나 가지고 sum[right] - sum[left]를 매번했는데, 그럴 필요가 없다. 그냥 right++에는 sum += sequence[right]를, left++에는 sum -= sequence[left]를 해주면 된다.
4. 대신 left가 sequence.length에 도달해야지 끝난다.
   4-1 친절하게도 입출력 예 2번에 힌트를 줌 ㅎㅎ

요즘 주말 반납해갈정도로 바빠서 블로그에 한 달정도 밥을 못줬는데 자꾸 어디선가 꼬르륵 소리가 나서 들어와보니 블로그 굶어 죽을라한다..

밥 자주 줄게 ㅋㅋ

코드

import java.util.*;
class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0, 100000001};
        int[] sum = new int[sequence.length + 1];
        sum[0] = 0;
        int i, j;
        for(i = 1; i < sum.length; i++) 
        {
            sum[i] = sequence[i - 1] + sum[i - 1];
        }
        for(i = 0, j = 1; i != j && j != sum.length ; ) {
            if(j == sum.length - 1) {
                if(sum[j] - sum[i] == k && j - i - 1 < answer[1] - answer[0]) { 
                    answer[0] = i;
                    answer[1] = j - 1;
                }                
                i++;                
                continue;
            }
            if(sum[j] - sum[i] == k && j - i - 1 < answer[1] - answer[0]) { 
                answer[0] = i;
                answer[1] = j - 1;
                i++;
            } else if(sum[j] - sum[i] < k) {
                j++;
            } else {
                i++;
            }
        }
        
        return answer;
    }
}