สมมติว่าเรามีรายการที่ประกอบด้วยค่าเพียงสองค่าคือ 1 และ -1 เราต้องการหาความยาวของรายการย่อย (sublist) ที่มีผลรวมเท่ากับ 0
เช่น ถ้าข้อมูลนำเข้าคือ nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1] ผลลัพธ์จะเป็น 8 เนื่องจากรายการย่อยที่ยาวที่สุดคือ [-1, 1, 1, -1, 1, -1, 1, -1] ซึ่งมีผลรวมเท่ากับ 0
ขั้นตอนการแก้ปัญหา
- สร้างตารางแฮช (hash map) ว่างชื่อ
table - กำหนด
cs = 0(prefix sum) และmax_diff = 0 - วนลูป
iตั้งแต่ 0 ถึงขนาดของnums- 1:- อัปเดต
cs := cs + nums[i] - ถ้า
cs == 0ให้max_diff := max(i + 1, max_diff) - ถ้า
csอยู่ในtableแล้ว ให้max_diff := max(max_diff, i - table[cs]) - มิฉะนั้น ให้บันทึก
table[cs] := i
- อัปเดต
- คืนค่า
max_diff
ตัวอย่างโค้ด
class Solution:
def solve(self, nums):
table = {}
cs = 0
max_diff = 0
for i in range(len(nums)):
cs += nums[i]
if cs == 0:
max_diff = max(i + 1, max_diff)
if cs in table:
max_diff = max(max_diff, i - table[cs])
else:
table[cs] = i
return max_diff
ob = Solution()
nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1]
print(ob.solve(nums))
ข้อมูลนำเข้า
[1, 1, -1, 1, 1, -1, 1, -1, 1, -1]
ผลลัพธ์
8
