178870. 연속된 부분 수열의 합

문제

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

제한사항

풀이

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int n = sequence.length;
        
        answer[0] = 0; answer[1] = n-1;
        
        int left =0;
        
        int sum = 0;
        
        for(int right = 0; right < n ; right ++ ) {
            sum+=sequence[right];
            
            while(sum > k && left < right) {
                sum-=sequence[left];
                left++;
                
            }
            
            if(sum == k) {
                // 부분 수열 길이 비교
                if((right-left+1) < (answer[1] -answer[0] +1)) {
                    answer[0] = left;
                    answer[1] = right;
                }
            }
        }
        return answer;
    }
}

회고

부분 수열 합이 k가 되는 수열 중 길이가 짧은 부분 수열의 양 끝 인덱스를 구하는 문제였다. 단순 이중 for문을 통해 부분 수열의 합이 k와 일치하는지 계산해볼 수 있지만, 제한사항에 따라 시간 초과가 발생한다. 그래서 투 포인터 알고리즘를 이용해 부분 수열을 찾았다. 수열이 정렬되어 있다면 투 포인터 알고리즘 시간 복잡도는 O(N)이다.