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

문제 링크 ▶︎ 프로그래머스 연속된 부분 수열의 합

문제 파악

5 ≤ sequence의 길이 ≤ 1,000,000 , sequence는 비내림차순으로 정렬되어 있습니다.
라는 조건이 있어 O(nlogn) 도 어려울 것 같다. 그리고 정렬된 정수 배열이라 정렬된 것을 이용하면 좋을 것 같다.
배열을 한번에 돌면서 체크하는 방법을 고려해야 한다.

접근 방법

비내림차순으로 정렬된 정수 배열이기 때문에 투포인터로 시작점에 i, j 를 두고 시작한다.
처음에 이동은 j++ 만 시키다가 sum이 k보다 커지면 i++ 로 sum을 낮추며 이동한다.

만약 sum이 k와 같아진다면 그것이 해당 i,j 가 정답이 될 수 있는 후보가 된다. 우선 answer 배열에 i,j 를 저장해두고, 만약 이후 계산에서 i-j 차이가 더 적은 i,j 가 나온다면 그 때 바꿔준다.

코드 구현

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int i = 0, j = 0, sum = 0;
        int len = 1000000, left = 0, right = 0;
        while (j < sequence.length) {
            sum += sequence[j];
            while (sum >= k) {
                if ((sum == k) && (j - i < len)) {
                    len = j - i;
                    answer[0] = i;
                    answer[1] = j;
                }
                sum -= sequence[i];
                i++;
            }
            j++;
        }
        return answer;
    }
}

개선 사항

정렬된 배열이기 때문에 투포인터를 사용해야겠다고 생각했지만 시작점이 같은 투포인터가 어색해서 조금 어려웠다.
투포인터에 확실히 그림을 그려보고 구현하는 것이 틀리지 않고 빠르게 풀 수 있는 방법인 것 같다.