Chương trình tìm số danh sách con có tổng k trong danh sách nhị phân bằng Python

Giả sử chúng ta có một danh sách nhị phân với 0 hoặc 1s. Chúng ta cũng có một đầu vào khác được gọi là k, chúng ta phải tìm số lượng danh sách con có tổng bằng k.

Vì vậy, nếu đầu vào giống như nums =[1, 0, 0, 1, 1, 1, 0, 1] k =3, thì đầu ra sẽ là 8 vì danh sách con là [1,0,0,1,1 ], [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].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sums:=một bản đồ ban đầu chứa valye 1 cho khóa 0
• r_sum:=0
• ans:=0
• đối với mỗi x trong nums, thực hiện
  • r_sum:=r_sum + x
  • ans:=ans + (tổng [r_sum - k] nếu (r_sum - k) là có, nếu không thì 0)
  • tổng [r_sum]:=1 + (tổng [r_sum - k] nếu (r_sum - k) có mặt, nếu không thì 0)
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[1, 0, 0, 1, 1, 1, 0, 1], 3

Đầu ra

8