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

제한 사항

분석

• 합 k가 매개변수로 주어졌을 때, 수열에서의 총 합을 구했을 때, 합이 k와 같을 경우 해당 수열의 첫 자릿수를 찾고 마지막 자릿수를 (i,j) 형식으로 배열로 저장한다.
• 해당 하는 k의 합의 배열을 저장해둔 값에서 j-i를 했을 때 가장 최솟값을 구하여 그 해당하는 배열을 출력한다.

이렇게 수열로 연속된 인덱스의 합을 구하는 문제에는 투 포인터를 사용하는 것이 편하다.

class Solution {
     public int[] solution(int[] sequence, int k) {

        // 투 포인터 (lt, rt), 누적합 (sum), 현재 포인터 간 길이 (ptrLen) 초기화
        int lt = 0;
        int rt = 0;
        int ptrLen = Integer.MAX_VALUE;
        int sum = 0;
        int[] answer = new int[2];
        while (rt < sequence.length && lt <= rt) {

            // 첫 번째 접근 또는 rt가 바라보는 원소가 k와 같을 때
            if (lt == rt) {
                sum = sequence[lt];
            }

            // 현재 누적합이 k와 같은 경우
            if (sum == k) {

                // 현재 포인터 간 길이가 이전 포인터 간 길이보다 짧은 경우
                if (ptrLen > rt - lt + 1) {
                    ptrLen = rt - lt + 1;
                    answer[0] = lt;
                    answer[1] = rt;
                }

                // 모든 원소는 양수이기 때문에 다음 경우의 수를 찾기 위해 lt를 증가 시킬 것이며, 누적합 계산을 위해 현재 sequence[lt] 값을 빼준다.
                sum -= sequence[lt];

                // rt도 마찬가지로 증가시킬 것이기 때문에 현재 누적합에 sequence[rt + 1]을 더해준다.
                if (rt + 1 < sequence.length) {
                    sum += sequence[rt + 1];
                }

                // 두 포인터가 같은 경우 가장 짧은 길이이기 때문에 순회를 종료
                if (lt == rt) {
                    break;
                }

                // 각 포인터 증가
                lt++;
                rt++;

            } else if (sum > k) {
                // 누적합이 k 보다 큰 경우 lt를 증가해가며 k와 같은 지를 비교
                sum -= sequence[lt];
                lt++;
            } else if (sum < k) {
                // 누적합이 k 보다 작은 경우 rt를 증가해가며 k와 같은 지를 비교
                if (rt + 1 < sequence.length) {
                    sum += sequence[rt + 1];
                }
                rt++;
            }

        }
        return answer;
    }
    
    
}