【每日一题20220513】最长零串

[hogwarts (霍格沃兹测试学院官方)]

‍ 给定一个数字列表，请编写一个函数，找出其中长度最长的总和等于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]

[1073434718_2599]

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]

[joyoko (徐子宇)]

神速 666

[joyoko (徐子宇)]

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)

[joyoko (徐子宇)]

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

[llbai]

可以使用滑动窗口思维

[ghost]

这是什么软件

[1092939085 (YX)]

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]

[lsh127k]

计算前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]

[HLK]

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]) == "没有符合条件的结果"

[llbai]

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

[sophia_he]

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]

[saberpan (潘修琦)]

[1304543605_9753]

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

[455018255_7468]

def solution(nums: list)-> list:
    # your code here
    long = []
    for i in range(len(nums) - 1):
        for j in range(i + 1 , len(nums)):
            if sum(nums[i:j]) == 0 and len(nums[i:j]) >= len(long):
                long = nums[i:j]
    return long


# 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]

[lirish]

def solution(nums: list)-> list:
    idx_list = []
    max = 0
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if sum(nums[i:j]) == 0:
                if j - i > max:
                    max = j - i
                    idx_list = [i,j]

    return nums[idx_list[0]:idx_list[1]]


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]

[lekaixin (ALe阿乐)]

def solution(nums: list)-> list:
    left_step=0
    res_list=[]
    dict={}
    while left_step<len(nums):
        for right_step in range(left_step+1,len(nums)):
            if sum(nums[left_step:right_step])==0:
                res_list.append(nums[left_step:right_step])
            else:
                continue
        left_step+=1
    for i in range(len(res_list)):
        dict[len(res_list[i])]=res_list[i]
    res_len_list=list(dict.keys())
    res_len_list.sort(reverse=True)
    res=[i[1] for i in dict.items() if i[0]==res_len_list[0]]
    return res[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]