【每日一题20220513】最长零串

:mage:‍ 给定一个数字列表,请编写一个函数,找出其中长度最长的总和等于0的连续字串。数字允许出现正数和负数。

【示例】
输入:[1, 2, -3, 7, 8, -16]
输出:[1, 2, -3]
解释:连续相邻且总和为0的最长串就是1, 2, -3。

题目难度:中等
题目来源:CodeWars-Longest sequence with zero sum

def solution(nums: list)-> list:
    # your code here

assert solution([1, 2, -3, 7, 8, -16]) == [1, 2, -3]
assert solution([25, -35, 12, 6, 92, -115, 17, 2, 2, 2, -7, 2, -9, 16, 2, -11]) == [92, -115, 17, 2, 2, 2]
def solution(nums: list)-> list:
    # your code here
    max_sublist = []
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if sum(nums[i:j]) == 0 and len(nums[i:j]) > len(max_sublist):
                max_sublist = nums[i:j]
    return max_sublist

assert solution([1, 2, -3, 7, 8, -16]) == [1, 2, -3]
assert solution([25, -35, 12, 6, 92, -115, 17, 2, 2, 2, -7, 2, -9, 16, 2, -11]) == [92, -115, 17, 2, 2, 2]
1 Like

神速 666

def solution(nums: list)-> list:
    # your code here
    a = []
    for i in range(n := len(nums)):
        m = i+1
        while m < n:
            if sum(r := nums[i:m]) == 0:
                a.append(r)
            m += 1
    if len(a) < 1:
        return a[0]
    else:
        return max(a)
def solution(nums: list)-> list:
    # your code here
    num_list = []
    for i in range(n := len(nums)):
        for j in range(i+1, n):
            if sum(r := nums[i:j]) == 0 and len(r) > len(num_list):
                num_list = r
    return num_list

可以使用滑动窗口思维

这是什么软件 :flushed:

def solution(nums: list) -> list:
    result = []
    l = len(nums)
    for i in range(l):
        for j in range(i + 1, l + 1):
            data = nums[i:j]
            if sum(data) == 0 and len(data) > len(result):
                result = data
    return result


assert solution([1, 2, -3, 7, 8, -16]) == [1, 2, -3]
assert solution([25, -35, 12, 6, 92, -115, 17, 2, 2, 2, -7, 2, -9, 16, 2, -11]) == [92, -115, 17, 2, 2, 2]

计算前n个数字的和,如果和相等,代表中间的数字和为0,时间复杂度O(n)

def solution(nums: list) -> list:
    sums = {}
    # 第一个元素为当前最长零串长度,第二个元素为起始索引
    max_zero = [-1, 0]
    sum_prefix = 0
    for i, v in enumerate(nums):
        sum_prefix += v
        if sum_prefix in sums:
            print(sums, sum_prefix, i)
            if i - sums[sum_prefix] > max_zero[0]:
                max_zero[0] = i - sums[sum_prefix]
                max_zero[1] = sums[sum_prefix] + 1
        else:
            sums[sum_prefix] = i
    if sums.get(0, -1) > max_zero[0]:
        max_zero[0] = sums[0] + 1
        max_zero[1] = 0
    return nums[max_zero[1]: max_zero[1] + max_zero[0]]


if __name__ == '__main__':
    assert solution([1, 2, -3, 7, 8, -16]) == [1, 2, -3]
    assert solution([25, -35, 12, 6, 92, -115, 17, 2, 2, 2, -7, 2, -9, 16, 2, -11]) == [92, -115, 17, 2, 2, 2]
1 Like
def solution(nums: list):
    new_list = []
    i=0
    while i < len(nums):
        for j in range(i,len(nums[i:])):
            if sum(nums[i:j+1]) == 0:
                new_list.append(nums[i:j+1])
        i += 1
    if len(new_list) == 0:
        return "没有符合条件的结果"
    else:
        new_list.sort(key=len,reverse=True)
        return new_list[0]

assert solution([1, 2, -3, 7, 8, -16]) == [1, 2, -3]
assert solution([25, -35, 12, 6, 92, -115, 17, 2, 2, 2, -7, 2, -9, 16, 2, -11]) == [92, -115, 17, 2, 2, 2]
assert solution([1,2,3]) == "没有符合条件的结果"

不好意思,没有注意到回复
这个是题目的出处的网站,可以提交代码检验代码是否正确

def solution(nums: list)-> list:
    longList=[]
    while(len(nums)>2):
        newList=[]
        sum=0
        for i in nums:
            sum=sum+i
            newList.append(i)
            if((sum ==0) & (len(newList)>len(longList))):
                longList=newList.copy()
        nums.pop(0)
    return longList

assert solution([1, 2, -3, 7, 8, -16]) == [1, 2, -3]
assert solution([25, -35, 12, 6, 92, -115, 17, 2, 2, 2, -7, 2, -9, 16, 2, -11]) == [92, -115, 17, 2, 2, 2]

image

def solution(nums: list)-> list:
    curr_max_ln = 0
    curr_max_substr =None
    for i in range(len(nums)):
        sum = nums[i]
        for j in range(i+1,len(nums)):
            sum =sum +nums[j]
            if sum == 0 and curr_max_ln< j-i+1:
                curr_max_ln = j-i+1
                curr_max_substr =nums[i:j+1]
    return curr_max_substr
关闭