[프로그래머스 level2] 연속된 부분 수열의 합 자바 투포인터 방식

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

프로그래머스

문제

오름차순 수열 sequence로부터 임의의 두 값을 선택해 만든 부분 수열의 합이 k가 되는 부분 수열을 구하시오.

부분수열은 아래의 조건을 만족해야 한다.

조건

기존 수열에서 선택한 두 원소 사이의 모든 원소를 포함하는 수열.
이 부분 수열의 합 = k 이며 k가 되는 수열이 여러개일 경우 가장 짧은 수열을 찾는다.
동일한 길이의 수열이 여러개인 경우, 시작 인덱스가 작은 쪽을 우선한다.

접근

오름차순 수열에서 연속된 구간의 합을 계산하면서 원하는 범위를 찾아야 한다.
이러한 문제는 투포인터 방식이 유효하다고 한다.

 

✅ 핵심 아이디어: Two Pointer (슬라이딩 윈도우)

1. 수열은 오름차순이므로, 연속된 구간의 합을 계산하면서 포인터를 앞뒤로 움직이는 방식 사용.
2. start, end 두 포인터를 정의해 구간을 조절.
3. 현재 구간의 합 sum이 k보다 작으면 end를 오른쪽으로 이동.
4. sum이 k보다 크면 start를 오른쪽으로 이동.
5. sum == k인 경우:  지금까지 발견된 가장 짧은 구간인지 확인하고 갱신

---

public int[] solution(int[] sequence, int k) {
        //start, end 두 포인터를 정의해 구간을 조절.
        int s = 0, e = 0, sum = sequence[0];
        int minLen = Integer.MAX_VALUE;
        int[] answer = new int[2];

        while(e < sequence.length){
            if(sum < k){ //현재 구간의 합 sum이 k보다 작으면 end를 오른쪽으로 이동.
                e ++;
                if(e < sequence.length) {
                    sum += sequence[e];
                }
            } else if(sum > k) { // sum이 k보다 크면 start를 오른쪽으로 이동.
                sum -= sequence[s];
                s ++;
            } else { //sum == k -> 지금까지 발견된 가장 짧은 구간인지 확인하고 갱신
                if( e - s < minLen){
                    minLen = e - s;
                    answer[0] = s;
                    answer[1] = e;
                }
                sum -= sequence[s];
                s ++;
            }
        }
        return answer;
    }