[Programmers] 연속된 부분 수열의 합 / ⭕

프로그래머스

 

1. 제출 코드 (34분 26초)

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int sum = 0;
        int end = 0;
        int len = Integer.MAX_VALUE;
        for(int start = 0; start < sequence.length; start++) {
        	// sum이 k보다 작을 때까지 end index 증가
            while(sum < k && end < sequence.length) {
                sum += sequence[end];
                end++;
            }
        	
            // sum == k 일때, 가장 짧은 길이의 부분 합을 정답으로 처리
            if(sum == k) {
                if(len > end - start) {
                    answer[0] = start;
                    answer[1] = end - 1;
                    len = end - start;
                }
            }
            // sum이 k보다 클 때, start index 증가
            sum -= sequence[start];
        }
        return answer;
    }
}

 

2. 유의할 점

• sequence의 길이가 1,000,000이므로 for문 2개를 이용하면 무조건 시간초과가 날 것 같았다.
• 해당 문제를 풀기전에 우연히 투포인터를 공부했고 생각이 나서 풀 수 있었다.