หา subarray ไม่ทับซ้อนสูงสุดที่ sum = target ใช้ prefix sum และ set เก็บ prefix sums ที่ผ่านมา: ถ้า prefix - target อยู่ใน set -> เจอ subarray เพิ่ม ans, reset set ใหม่เก็บแค่ prefix ปัจจุบัน (ป้องกัน overlap) มิฉะนั้นเพิ่ม prefix ลง set
ขั้นตอนการทำงาน
- t = set([0]), temp = 0, ans = 0
- วนลูปแต่ละ i ใน nums: temp += i
- prev = temp - target
- ถ้า prev ใน t: ans++, t = set([temp])
- มิฉะนั้น: t.add(temp)
- คืน ans
ตัวอย่างโค้ด
def solve(nums, target):
t = set([0])
temp = 0
ans = 0
for i in nums:
temp += i
prev = temp - target
if prev in t:
ans += 1
t = set([temp])
else:
t.add(temp)
return ans
nums = [3, 2, 4, 5, 2, 1, 5]
target = 6
print(solve(nums, target)) # Output: 2
อินพุต/เอาต์พุต
Input: [3,2,4,5,2,1,5], target=6 Output: 2
Subarrays: [2,4] และ [1,5] ผลรวม = 6
