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

링크

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

프로그래머스

 

풀이

처음에는 완전탐색으로 풀었지만 실패했다.

 

투포인터로 변경 후 적용으로 완료하였다.

 

자세한 설명은 이 분 블로그에 친절하게 잘 되어 있어서 링크를 남긴다.

 

 

class Solution {
    public int[] solution(int[] sequence, int k) {
        for (int i=0; i<sequence.length; i++) {
            if (sequence[i] == k) {
                return new int[]{i, i};
            }   
        }
        
        int startIndex = 0;
        int endIndex = 1;
        int currentSum = sequence[0];
        int minSize = sequence.length;
        int[] answer = new int[2];
        while(startIndex < endIndex) {
            if (currentSum == k) {
                // 아래에서 더하고 endIndex를 바로 더해줬기 때문에 실제 index 계산 시에는 endIndex-1을 해줘야 함
                if (minSize > endIndex-1 - startIndex) {
                    minSize = endIndex-1 - startIndex;
                    answer[0] = startIndex;
                    answer[1] = endIndex-1;   
                }
            }
            
            if (currentSum < k && endIndex < sequence.length) {
                currentSum += sequence[endIndex];
                endIndex++;
            } else {
                currentSum -= sequence[startIndex];
                startIndex++;
            }
        }
        
        return answer;
    }
}