[프로그래머스] 연속된 부분 수열의 합(178870)

1. 문제 풀이 아이디어

• 두 포인터 알고리즘을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int l = -1, r = 0;
        int sum = sequence[0];
        int length = Integer.MAX_VALUE;
        while (l < r && r < sequence.length) {
            if (sum == k) {
                if (r - l < length) {
                    length = r - l;
                    answer[0] = l + 1;
                    answer[1] = r;
                }
                l++;
                sum -= sequence[l];
            } else if (sum < k) {
                r++;
                if (r < sequence.length) {
                    sum += sequence[r];
                }
            } else {
                l++;
                sum -= sequence[l];
            }
        }
        return answer;
    }
}

3. 정리

• 왼쪽 포인터 l은 1, 오른쪽 포인터 r은 0으로, sum은 sequence[0]의 값으로 초기화한 후, 두 포인터 알고리즘을 사용한다.

• sum이 k와 같으면, 현재 구간의 길이가 기존 구간의 길이보다 짧을 경우 결과값을 갱신하고, 왼쪽 포인터를 한 칸 이동한다.

• sum이 k보다 작으면 오른쪽 포인터를 이동하고, r이 sequence의 길이보다 작다면 sum에 sequence[r] 값을 더한다.

• sum이 k보다 크면 왼쪽 포인터를 이동시키고, sum에서 sequence[l] 값을 뺀다.

• 이 과정을 l이 r보다 작고, r이 sequence의 길이보다 작을 동안 반복하여 문제를 해결한다.