(LEVEL 2)프로그래머스 - 연속된 부분 수열의 합 (JAVA) 투포인터

문제

---

입출력 예

---

접근방법

1. 투포인터를 사용해서 풀이

 

 

풀이.

1. answer를 길이 2만큼 선언해준다.

2. 투포인터로 돌아갈 lt, rt를 선언하고 k와 비교할 sum을 선언해준다.

3. 여기서 문제를 제대로 안읽어서 처음에 통과를 못했는데, 답이 여러개 일 때 길이가 짧은수열이 우선순위이고 길이가 동일한 길이의 수열이 여러개일 경우 가장 앞쪽(시작 인덱스가 작은 쪽) 수열을 찾는다.(이 조건을 만족시키기위해 수열의 길이를 큰값으로 선언)

4. rt를 sequence의 길이만큼 반복하며 더해주고, 수열의 합이 같으면서, 정답의 길이가 더 작을 때 수열의 인덱스를 정답으로 갱신시켜주고 길이 또한 갱신시켜준다.

5. 만약 rt를 더해준 값이 sum보다 크다면 같거나 작아질 때 까지 lt를 증가시키며 해당 값을 빼준다.

빼준다음 sum이랑 k가 같아질수도 있으니 한번더 확인

 

---

코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int lt=0;
        int sum=0;
        int L = sequence.length;
        int len = Integer.MAX_VALUE;
        for(int rt=0;rt<L;rt++){
            sum+=sequence[rt];
            if(sum==k && rt-lt < len){
                answer[0]=lt;
                answer[1]=rt;
                len = rt-lt;
            }
            while(sum>k){
                sum-=sequence[lt++];
                if(sum==k && rt-lt < len){
                    answer[0]=lt;
                    answer[1]=rt;
                    len = rt-lt;
                }
            }
        }
        return answer;
    }

}