資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：查詢和為0的最長子列表的長度
假設我們有一個列表，其中只有兩個值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
對於 i 從 0 到 nums 的大小 - 1，執行：
cs := cs + nums[i]
如果 cs 等於 0，則
max_diff := i + 1 和 max_diff 的最大值
如果 cs 存在於 table 中，則
max_diff := 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
更新於：2020年12月15日
瀏覽量：105
廣告