โปรแกรมนับจำนวนสับลิสต์ที่ผลรวมเท่ากับเป้าหมายใน Python

สมมติว่ามีรายการตัวเลข nums และค่า target ต้องการหาจำนวนสับลิสต์ (subarrays) ที่ผลรวมเท่ากับ target

ตัวอย่าง: nums = [3, 0, 3], target = 3 ผลลัพธ์คือ 4 สับลิสต์คือ [3], [3, 0], [0, 3], [3]

ขั้นตอนการแก้ปัญหา

1. สร้าง map temp ว่าง, ตั้ง temp[0] = 1
2. s = 0 (prefix sum), ans = 0
3. วนลูปแต่ละ index i:
   • s += nums[i]
   • comp = s - target
   • ถ้า comp อยู่ใน temp: ans += temp[comp]
   • temp[s] += 1
4. คืนค่า ans

ตัวอย่างโค้ด

from collections import defaultdict

class Solution:
    def solve(self, nums, target):
        temp = defaultdict(int)
        temp[0] = 1
        s = 0
        ans = 0
        for i in range(len(nums)):
            s += nums[i]
            comp = s - target
            if comp in temp:
                ans += temp[comp]
            temp[s] += 1
        return ans

ob = Solution()
nums = [3, 0, 3]
target = 3
print(ob.solve(nums, target))

อินพุต

[3, 0, 3], 3

เอาต์พุต

4