[프로그래머스] 연속된 부분 수열의 합 (Java) - 투포인터

문제 파악

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

프로그래머스

 

오름차순으로 정렬된 sequence배열에서 연속부분수열의 합이 k값이 되는 구간을 찾는 문제

• 부분 수열이 여러 개인 경우 길이가 짧은 수열 반환
• 길이가 짧은 수열이 여러 개일 경우 앞쪽(시작 인덱스가 작은) 수열 반환

 

 

 

 

접근 방법

전형적인 구간 합 문제 (투포인터)

 

구간 합을 구할 때는, left 포인트와 right 포인트를 지정해 준 후,

1) 구간 합(total) < target 일 경우

    현재 left가 위치한 부분을 빼준 후, ⇒ total -= arr[left];

2) 구간 합(total) > target 일 경우

    right 증가 시켜준 뒤 ⇒ right++;

3) 구간 합 == target일 경우

    문제에 해당하는 조건에 맞춰, 출력 !

• 이 문제에서는 기존 구했던 부분 배열의 길이보다, 현재 구한 부분 배열이 더 짧으면, 업데이트

• right가 위치한 부분 더해주기 ⇒ total += arr[right];
• left 증가 시키기 ⇒ left++;

 

 

 

 

코드 구현

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0, 1_000_000};
        int left = 0;
        int total = 0;
        int n = sequence.length;
        for(int right=0; right<n; right++){
            total += sequence[right];
            while(total>k){
                total -= sequence[left];
                left++;
            }
            if(total==k){
                if((answer[1]-answer[0])>(right-left)){
                    answer[0] = left;
                    answer[1] = right;
                }
            }
        }
        return answer;
    }
}