剑指offer57-- 和为s的连续正数序列

剑指offer57-- 和为s的连续正数序列

题目

题目的意思是给定一个s,找印出所有的和为s的连续正数序列(至少有两个元素),

之前做的类似的是数组是给定的,然后从数组中找到连续的子数组使得其和为s,而现在相当于数组已经给定了,即全体正整数列,然后现在经定s,要找到和为s所有的充列

这个题可以利用上面一个题的双指针的办法,感觉双指针的办法适合排好序的,因为如果没有排序的话,大了小了不知道该往哪里走了.

def main(s):
    # s>=3
    assert s>=3

    small = 1  # 这两个不再指的是index了在这里,但是如果更general的排好序的数组的话可以用这个作为index
    big = 2
    
    middle = (s+1)/2
    summ = small+big # 初始化和
    
    ret =  []

    while small < middle:
        if summ == s:
            ret.append(list(range(small, big+1))) 
    
        while small<middle and summ>s:
            # 当前的和比较大,需要去掉左边的数
            summ -= small
            small += 1

            # 删除了之后再判断
            if summ==s:
                ret.append(list(range(small, big+1))) 
            
        
        # 这时候说明summ<=s: 但是等于的时候在里面已张处理了,所以外边只用处理summ相加的情况
        big += 1
        summ += big
                     
    return ret
        

测试结果如下

pengkun@pc:~/github/exercise$ python jianchi57-2.py 5
[[2, 3]]
pengkun@pc:~/github/exercise$ python jianchi57-2.py 15
[[1, 2, 3, 4, 5], [4, 5, 6], [7, 8]]
pengkun@pc:~/github/exercise$ python jianchi57-2.py 35
[[2, 3, 4, 5, 6, 7, 8], [5, 6, 7, 8, 9], [17, 18]]

详细解释的


def get_continuous_array(n):
    assert n>=3, "please input a number which is bigger than 2."
    if n==3:
        return [1,2]

    small, big = 1,2
    thresh = (n+1)//2  # 这个是作为thresh的,因为最终要得到的序列的左端点不会超过这个.

    summ = small + big
    ret = []
    while small < thresh:
        if summ == n:
            ret.append(list(range(small, big+1)))
        while small < thresh and summ > n:
            summ -= small    # 如果去掉右边的话,得到的就不是连续的了,
            small += 1

            # 上面的弄完了之后要重新判断一下
            if summ == n:
                ret.append(list(range(small, big+1)))

        # summ < n
        big += 1
        summ += big

    return ret

def main():
    for i in range(30, 40):
        print(get_continuous_array(i))

if __name__ == '__main__':
    main()


其实也可以用之前leetcode560题的想法,

如下

def test2(s):
    assert s>=3

    #nums = list(range(1,100))  # 需要包括0,不然当前n项和
    nums = list(range(1,(s+1)//2+1))
    summ = 0
    dic={}
    ret = []
    for i in nums:
        summ += i
        # 要先判断当前的和是不是s
        if summ == s:
            ret.append(list(range(1,i+1)))
        if summ-s in dic:
            ret.append(list(range(dic[summ-s]+1, i+1)))
        dic[summ] = i

    return ret

这两种复杂度都挺低的,都可以用,不过第一个方法好像只适合于排好序的数组,而第二个则可以应用于任意的数组都是可以的.不过要注意和第560题的区别.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦