프로그래머스 - 연속된 부분 수열의 합

프로그래머스 - 연속된 부분 수열의 합

주어진 수열과 정수 k의 대해, 부분수열의 합이 k가 되게 하는 구간을 구하는 문제입니다. 부분수열의 구간을 작게 만들어야 하므로 투 포인터를 이용하여 구간의 길이를 비교했습니다.

구간합이 k보다 작으면 뒤쪽 포인터를 전진시켜 구간합을 늘려야합니다.

구간합이 k보다 크면 앞쪽 포인터를 전진시켜 구간합을 줄입니다.

구간합이 k일 때, 구간의 길이가 이전에 구한 구간길이보다 짧으면 갱신합니다.(같으면 앞쪽 인덱스가 작은 것을 반환해야 하므로 pass) 그리고 앞 뒤 포인터를 모두 전진시킵니다. 수열의 원소가 0보다 크다는 조건이 있기 때문입니다.

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[] {0, 0};
        int forth = 0;
        int sum = 0;
        int len = 1_000_000;
        
        for (int back = 0; back < sequence.length; back++) {
            sum += sequence[back];
            
            if (sum == k) {
                if (len > back - forth) {
                    answer[0] = forth;
                    answer[1] = back;
                    len = back - forth;
                }
                sum -= sequence[forth];
                forth++;
                continue;
            }
            
            if (sum > k) {
                sum -= sequence[forth];
                forth++;
                sum -= sequence[back];
                back--;
            }
        }
        
        return answer;
    }
}