연속된 부분 수열의 합

문제 정보

• 문제 링크
• 난이도: Lv.2
• 문제 유형: 탐색, 슬라이딩 윈도우

풀이

슬라이딩 윈도우를 사용하는 문제다.

다만 이하 두 조건 때문에, 합이 k인 부분 수열을 찾고 끝내는 것이 아니라 주어진 배열 sequence의 끝까지 탐색해야 한다.

• 합이 k인 부분 수열이 여러 개인 경우 가장 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

코드

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