数据结构
网络
关系数据库管理系统 (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
广告