Algorithm Subarray zero sum
알고리듬 Subarray zero sum을 알아보겠습니다.
[-4, 7, -2, 2, -7, 12, 0, 4, 9]
다음과 같은 배열이 있을 때, 0이 되는 배열의 일부분은 (7, -2, 2, -7), (-2, 2), 0 이렇게 3 가지 경우가 있습니다.
이것을 코드로 어떻게 구할 수 있을까요?
Hash 함수를 이용합니다.
Python의 Dictionary는 Hash를 이용합니다.
7 + 0 = 7을 이용하면 됩니다.
즉, 무엇인가 더했을 때, 동일한 값이 나온다면 0을 더한 것과 같다는 뜻입니다.
아래 코드를 보면, Dictionary에 이전에 봤던 값들을 넣습니다.
그러다가 무엇인가 더하고 빼기를 진행했는데, 이 값이 Dictionary의 Key 값으로
존재한다면 0을 더한 것으로 판단하면 됩니다.
카테고리: Algorithm
댓글
댓글 쓰기
궁금한 점은 댓글 달아주세요.
Comment if you have any questions.