[Array, Hash] Subarray Sum Equals K

연속된 element로 구성된 nums의 부분집합 중, 합이 k가 되는 부분집합의 갯수를 리턴하라

 

각 부분합을 원소로 표현한 sum이라는 배열을 만들고, map이라는 딕셔너리를 만들었다.

그 후 sum에서 k를 뺀 값이 key로 딕셔너리에 존재하면 answer를 하나 추가해주었고,

그렇지 않으면 sum만 딕셔너리에 추가해주었다.

 

사실 골머리를 앓았던 문제라서 도식으로 정리해보았다.

두번째를 예시로 들어본다.

[ 0, 1, 2, 3 ]이라는 배열이 들어왔을 때, 각 element를 연쇄적으로 더한 sum이라는 배열을 만들었다.

얘는 [ 0, 1, 3, 6 ]이 될 것이다.

실제 주어진 배열은 [ 1, 2, 3 ] 이지만 1개의 원소만 가진 부분합도 카운팅되므로 편의상 0을 넣었다.

 

저렇게 만든 sum 배열을 확인해보면 6-3과, 3-0이 k의 값과 같아진다.

이는 nums의 0번,1번,2번 원소의 합과 3번 원소의 합(1개의 원소)이 k가 됨을 의미한다

왜냐하면 사실 저 배열은 [ num0 , num0+ num1 , num0+num1+num2, num0+num1+num2+num3] 이다.

만약 k=2로 주어진다면, (num0+num1+num2+num3) - (num0+ num1 )=2가 될것이다.

이 말의 뜻은 num2와 num3이라는 연속된 element로 구성된 부분합이 조건에 맞다는 뜻이 된다.

 

이러한 이유로 sum-k가 sum에 key로 존재할때 answer를 카운팅해주는 것이다.

정확히는 n번째 루프에서 sum[n] - sum[m] = key 조건을 만족하는 m이 존재하는지를 살피는 것이다.