인프런 커뮤니티 질문&답변

안녕하세요^^

부분수열에 음수가 있으면 슬라이딩 윈도우로는 해결되지 않습니다.

음수가 있을 때는 해싱을 사용해서 O(n)으로 해결할 수 있습니다.

참고로 2월 말쯤 나오는 후속강좌에 "음수가 있는 부분수열" 이라는 문제 제목으로 다루고 있습니다.

궁금하실 것 같아 코드 올려드릴께요. 스스로 분석해 보세요.

import java.util.*;
class Solution {
	public int solution(int[] nums, int m){
		int answer = 0;
		HashMap<Integer, Integer> nH = new HashMap<>();
		int sum = 0;
		nH.put(0, 1);
		for(int x : nums){
			sum += x;
			if(nH.containsKey(sum-m)) answer += nH.get(sum-m);
			nH.put(sum, nH.getOrDefault(sum, 0) + 1);
		}
		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2, 2, -3}, 5));	
		System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2}, 3));	
		System.out.println(T.solution(new int[]{-1, 0, 1}, 0));	
		System.out.println(T.solution(new int[]{-1, -1, -1, 1}, 0));	
	}
}