leetcode 面试题57 - II. 和为s的连续正数序列

96 阅读 0 评论 64 点赞

我是靠谱客的博主潇洒鸡，这篇文章主要介绍leetcode 面试题57 - II. 和为s的连续正数序列，现在分享给大家，希望可以做个参考。

https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/submissions/

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        # 对于一个数target，输出所有和为 target 的连续正整数序列
        ans=[]
        for i in range(1,target):
            L=[]
            sum=0
            for j in range(i,target):
                L.append(j)
                sum+=j
                if(sum==target):
                    ans.append(L)
                    break
                elif sum>target:
                    break
        return ans

模拟大法好
在这里插入图片描述
只是效率低
我写题目的习惯都是能解就先解出来，就算是很低级的解法也没关系。只有解出来之后才去思考更优化的解法，不然写半天一个解法都没想出来，挫败感很强。

下面尝试更多解法

two points
仔细分析一下，序列是连续的，并且很像滑动窗口，自然地想到了two points的思路

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        # 对于一个数target，输出所有和为 target 的连续正整数序列
        ans=[]
        i,j=1,1
        L=[i for i in range(target)]
        s=0
        while i<target//2+1:
            t=L[i:j]
            s=sum(t)
            if(s==target):
                ans.append(t)
                i+=1
            elif s>target:
                i+=1
            elif s<target:
                j+=1
        return ans

并且i的区间肯定是只取到target/2+1的整数，因为任何一个数的一半加上大于它一半的数可能会超过它了
在这里插入图片描述

再尝试优化一下，发现并不用每次都切片，只需要记录i，j和切片区间的和就行了

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        # 对于一个数target，输出所有和为 target 的连续正整数序列
        ans=[]
        i,j=1,1
        L=[i for i in range(target)]
        s=1
        while i<target//2+1:
            if(s==target):
                ans.append(L[i:j+1])
                s-=i
                i+=1
            elif s>target:
                s-=i
                i+=1
            elif s<target:
                j+=1
                s+=j
        return ans

又高了一点
在这里插入图片描述
想不到更好的方法了，贴一下题解
https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/mian-shi-ti-57-ii-he-wei-sde-lian-xu-zheng-shu-x-2/