연속된 부분 수열의 합 (자바, 프로그래머스)

풀이 아이디어

• 투포인터 알고리즘 활용
  시작 index를 s, 끝을 e 로 나타내어 한 칸씩 옮겨가며 목표합과 합을 비교, 같으면 조건에 따라 answer 갱신. 자세한건 주석을 참고해주세요!

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {};
        int s = 0; // 시작 인덱스
        int e = 0; // 끝 인덱스
        int sum = sequence[0]; // 시작~끝 의 합
        int len = sequence.length + 1;
        while(true){
            if(sum < k){
            	// e가 뒤로 더 갈 수 없으면 끝
                if(e == sequence.length - 1) break;
                e += 1;
                sum += sequence[e];
            }else if(sum > k){
            	// s가 뒤로 더 갈 수 없으면 끝
                if(s == sequence.length - 1) break;
                sum -= sequence[s];
                s += 1;
            }
            // s 또는 e 를 옮긴 후 sum 이 k와 같아진 경우 answer 갱신할지 살펴보기
            if(sum == k){
                if(len > (e-s+1)) {
                    // 기존 len 보다 지금 s,e 길이가 짧을 경우 answer 갱신
                    len = e-s+1;
                    answer = new int[]{s,e};
                }
                if(s == e){ 
                    // s와 e가 같다는 말은 길이가 1이란 뜻, 길이가 1이 나왔다면
                    // 이게 가장 짧고 가장 앞에 나아왔는 부분 수열이므로 while문 종료
                    break;
                }else{
                    // 뒤에 더 살펴보기 위해 강제로 s를 한 칸 뒤로 옮기기
                    sum -= sequence[s];
                    s += 1;
                }
            }
        }
        return answer;
    }
}