부분합을 구한 다음,
각 위치에 대해서 순차적으로 방문하면서, 처음부터 현재 위치까지의 부분합 중에 K를 만족하는 부분합의 개수를 구하면 됩니다.
부분합을 구하는대에는 O(N)이 필요하고, 처음부터 현재 위치까지의 부분합을 보는것도 O(N)이라 O(N^2)이 될 수 있지만,
처음부터 현재 위치까지의 부분합 중, 나에게 필요한것은 K - sum 하나 라는 사실을 이용하면
이 숫자를 갖는 부분합의 개수를 로그시간에 찾을 수 있습니다.
따라서 O(NlgN) 으로 답을 구할 수 있게 됩니다.
temp 8년 전 1
부분합을 구해서 처리하면될거같은데 최대가 20만이다보니..
모든 부분합을 구하기가 시간상 오버가 나네요..
힌트 부탁드립니다.
어떤방법을써야 모든 연속된 부분합을 구할수있을까요?