สมมติว่าเรามีรายการที่มีค่าเพียงสองค่าคือ 1 และ -1 เราต้องหาความยาวของรายการย่อยที่ยาวที่สุดที่มีผลรวมเป็น 0
ดังนั้น หากอินพุตเป็น nums =[1, 1, -1, 1, 1, -1, 1, -1, 1, −1] ผลลัพธ์จะเป็น 8 เนื่องจากรายการย่อยที่ยาวที่สุดคือ [-1 , 1, 1, -1, 1, -1, 1, −1] ซึ่งผลรวมเป็น 0
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
table :=แผนที่ใหม่เปล่า
-
cs :=0, max_diff :=0
-
สำหรับฉันในช่วง 0 ถึงขนาดของ nums − 1 ทำ
-
cs :=cs + nums[i]
-
ถ้า cs เหมือนกับ 0 แล้ว
-
max_diff :=สูงสุดของ i + 1 และ max_diff
-
-
ถ้า cs อยู่ในตารางแล้ว
-
max_diff :=สูงสุดของ max_diff และ (i - table[cs])
-
-
มิฉะนั้น
-
ตาราง[cs] :=ฉัน
-
-
-
คืนค่า 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
