0 또는 1이 있는 이진 목록이 있다고 가정합니다. 또한 k라는 또 다른 입력이 있습니다. 합이 k와 같은 하위 목록의 수를 찾아야 합니다.
따라서 입력이 nums =[1, 0, 0, 1, 1, 1, 0, 1] k =3과 같으면 하위 목록이 [1,0,0,1,1이기 때문에 출력은 8이 됩니다. ], [0,0,1,1,1], [0,0,1,1,1,0], [0,1,1,1], [0,1,1,1,0], [1,1,1], [1,1,1,0] [1,1,0,1].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- sums :=지도는 처음에 키 0에 대한 값 1을 포함합니다.
- r_sum :=0
- ans :=0
- 숫자 단위의 각 x에 대해 다음을 수행합니다.
- r_sum :=r_sum + x
- ans :=ans + ((r_sum - k)가 있는 경우 합계[r_sum - k], 그렇지 않으면 0)
- sums[r_sum] :=1 + ((r_sum - k)가 있으면 sums[r_sum - k], 그렇지 않으면 0)
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums, k):
sums = {0: 1}
r_sum = 0
ans = 0
for x in nums:
r_sum += x
ans += sums.get(r_sum - k, 0)
sums[r_sum] = sums.get(r_sum, 0) + 1
return ans
nums = [1, 0, 0, 1, 1, 1, 0, 1]
k = 3
print(solve(nums, k)) 입력
[1, 0, 0, 1, 1, 1, 0, 1], 3
출력
8