[프로그래머스/Lv. 2] 연속된 부분 수열의 합 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[] {0, sequence.length - 1};
        
        int left = 0;
        int right = 1;
        
        int sum = sequence[0];
        
        while(left < right) {
            if(sum == k) {
                change(right, left, answer);
                sum -= sequence[left++];
            }
            else if(sum > k) {
                sum -= sequence[left++];
            }
            else if(right < sequence.length) {
                sum += sequence[right++];
            }
            else {
                break;
            }
        }
 
        return answer;
    }
    
    private static void change(int right, int left, int[] answer) {
        if((right - 1 - left) < (answer[1] - answer[0])) { // 기존 left와 right 길이보다 짧다면 갱신
            answer[0] = left;
            answer[1] = right - 1;
        }
    }
}

 

 

🧩  해결 아이디어

• 투 포인터 

- 시간 복잡도 : O(N)

 

 

💥 유의사항

right가 배열 마지막 인덱스보다 커지더라도 멈추면 안 됨.

left가 줄어들면서 sum과 k가 같아지는 구간이 있을 수 있으므로.

 

---

🔺 다른 풀이들

- 정렬도 하셨고...

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

 

 

- 복습은 이것으로...

[프로그래머스 Level 2] 연속된 부분 수열의 합 (Java)

 

- 약간 내가 생각했던 풀이와 가장 비슷함.  Comparable compareTo로 정렬하셨다.

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

---

💬 느낀 점

투 포인터 문제 50만년만에 봐서 이거 쓸 생각도 못 했다...

다시 알고리즘의 세계로...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스] 연속된 부분 수열의 합 Lv2 JAVA [투포인터][엄탱]