목표 합을 갖는 부분 배열 개수 세기

이번에는 목표값 k가 되도록 더했을 때의 부분 배열이 몇 개인지 세어 보겠습니다. 모든 쌍을 확인하면 느리지만, 누적 합과 해시 맵을 함께 사용하면 해결할 수 있습니다. 🎯

부분 배열의 합은 prefix[r + 1]에서 prefix[l]을 뺀 값입니다. 따라서 합이 k라는 것은 두 누적 합 값의 차이가 정확히 k라는 뜻입니다.

현재 누적 합이 P라면, 이전에 나온 누적 합 중 P - k와 같은 값이 필요합니다. 이 식 변형이 핵심 아이디어의 전부입니다.

매번 뒤쪽을 다시 훑는 대신, 각 누적 합 값이 몇 번 나타났는지 기억하십시오. 누적 개수를 관리하면 O(1)에 답할 수 있습니다.

딕셔너리는 각 누적 합 값을 그 값이 나타난 횟수에 연결합니다. 이 맵을 사용하면 조회와 개수 세기를 즉시 수행할 수 있습니다.

반복문을 시작하기 전에 누적 합 0이 한 번 나타났다고 기록하십시오. 이 초기값 덕분에 인덱스 0에서 시작하는 부분 배열도 셀 수 있습니다.

각 원소마다 누적 합을 갱신하고, 필요한 값의 개수를 더한 다음, 현재 누적 합을 기록하십시오. 한 번의 순회로 모든 작업을 처리할 수 있습니다.

현재 누적 합을 기록하기 전에 답에 먼저 더해야 합니다. 그렇지 않으면 길이가 0인 구간이 끼어들어 개수가 잘못됩니다.

각 원소에서 상수 시간 작업만 수행하므로 전체 개수 세기는 O(n)에 끝납니다. 큰 입력에서는 O(n²) 완전 탐색보다 훨씬 빠릅니다.

슬라이딩 윈도와 달리 이 방법은 음수도 문제없이 처리합니다. 부호와 관계없이 누적 합의 차이가 항상 유효하기 때문입니다.

이 패턴은 유명한 부분 배열 합이 k가 되는 문제와, 대회 채점 문제에 다양한 형태로 등장하는 여러 변형을 해결합니다.

현재 누적 합은 P이고 목표값은 k입니다.

누적 합과 빈도 맵을 사용하면 목표 합을 갖는 부분 배열을 O(n)에 셀 수 있습니다. 누적 합 0을 초기화한 뒤, 현재 값을 기록하기 전에 개수를 세십시오. ✅