สมมติว่าเรามีรายการไบนารีที่มี 0s หรือ 1s นอกจากนี้เรายังมีอินพุตอื่นที่เรียกว่า k เราต้องหาจำนวนรายการย่อยที่มีผลรวมเท่ากับ k
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[1, 0, 0, 1, 1, 1, 0, 1] k =3 ผลลัพธ์จะเป็น 8 เนื่องจากรายการย่อยคือ [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].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ผลรวม :=ในแผนที่แรกประกอบด้วย valye 1 สำหรับคีย์ 0
- r_sum :=0
- ตอบ :=0
- สำหรับแต่ละ x เป็น nums ทำ
- r_sum :=r_sum + x
- ans :=ans + (sums[r_sum - k] ถ้า (r_sum - k) มี มิฉะนั้น 0)
- sums[r_sum] :=1 + (sums[r_sum - k] ถ้า (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
