[프로그래머스] Lv.2 : 연속된 부분 수열의 합 - 자바[Java]

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

풀이

5 ≤ sequence의 길이 ≤ 1,000,000  = 10^6 이기 때문에 O(n) 알고리즘을 사용해야 한다.

따라서 투포인터 알고리즘을 사용하여 문제를 풀었다.

코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int sum = sequence[0];
        int i = 0, j = 0;
        
        // 답이 [0, 0]인 경우
        if (sum == k) {
            return new int[]{0, 0};
        }
        
        int len = sequence.length + 1; // 중요!
        int startIdx = 0, endIdx = 0;
        
        while (i < sequence.length && j < sequence.length) {
            if (sum < k) {
                j++;
                if (j < sequence.length)
                    sum += sequence[j];
            } else if (sum > k) {
                sum -= sequence[i];
                i++;
            } else { // sum == k
                if (j - i + 1 < len) { // 길이가 더 짧은 수열인 경우
                    len = j - i + 1;
                    startIdx = i;
                    endIdx = j;
                }
                sum -= sequence[i];
                i++;
            }
        }
        
        int[] answer = new int[]{startIdx, endIdx};
        return answer;
    }
}