剑指offer-57-2

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例：

输入：target = 9
输出：[[2,3,4],[4,5]]

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

解法

方法一：暴力法

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        for start in range(1,target//2+1):
            temp_list = []
            temp_target = target
            for t in range(start,target//2+2):
                temp_list.append(t)
                temp_target -= t
                if temp_target == 0:
                    res.append(temp_list)
                    break
                elif temp_target < 0:
                    break
        return res

方法二：暴力+数学优化

方法一枚举每个正整数为起点，从起点开始累积 sum 和判断是否等于 $target$。注意到，如果我们知道起点 $x$ 和终点 $y$，那么 $x$ 累积到 $y$ 的和由 求和公式可知为：
$$
\frac{(x+y)\times (y-x+1)}{2}
$$
则问题转为，是否存在一个正整数 $y$，满足等式：
$$
\frac{(x+y)\times (y-x+1)}{2} = target
$$
转化后变为：
$$
y^2 + y - x^2 +x - 2\times target = 0
$$
这是关于 $y$ 的一元二次方程，其中 $a=1,b=1,c=-x^2+x-2\times target$ 直接套用求根公式解得 $y$，判断是否整数解需要满足两个条件：

• 判别式 $b^2-4ac$ 开根号需为整数
• 最后的求根公式的分子需要为偶数，因为分母为 2

class Solution:
    def findContinuousSequence(self, target: int):
        
        res = []

        for x in range(1,target//2 + 1):
            delta = 1 - 4 * (x - x*x - 2 * target)
            delta_sqrt = int(math.sqrt(delta))
            # print("---------",delta,delta_sqrt)
        
            if delta_sqrt * delta_sqrt == delta and  (delta_sqrt -1)%2 == 0:
                temp_list = []
                y = int((-1 + delta_sqrt) /2) # 另一个解(-1-delta_sqrt)/2必然小于0，不用考虑
                for i in range(x,y+1):
                    temp_list.append(i)
                
                res.append(temp_list)
                # print(y)

        return res

方法三：双指针

用两个指针 $l,r$ 表示当前枚举到的以 $l$ 为起点到 $r$ 的区间，$sum$ 表示 $[l,r]$ 的区间和，由求和公式$O(1)$求得为 $sum = \frac{(l+r) \times (r-l + 1)}{2}$ ，起始 $l=1,r=2$。

一共有3种情况：

• 如果 $sum < target$ 则说明指针 $r$ 还可以向右拓展使得 $sum$ 增大，此时指针 $r$ 向右移动，既 $r+=1$
• 如果 $sum > target$ 则说明以 $l$ 为起点，不存在一个 $r$，使得 $sum == target$，此时要枚举下一个起点，指针 $l$ 向右移动，既 $l+=1$
• 如果 $sum == target$，则说明找到了合法解 $[l,r]$ ，我们需要将 $[l,r]$ 的序列放进答案数组，且我们知道以 $l$ 为起点的合法解最多只有一个，所以枚举下一个起点，指针 $l$ 向右移动，，既 $l+=1$

class Solution:
    def findContinuousSequence(self, target: int):
        l,r = 1,2
        res = []
        while l < r:
            sum = int(((l+r) * (r -l + 1)) / 2)
            print(sum)
            if sum == target:
                temp_list = [i for i in range(l,r+1)]

                res.append(temp_list)
                l+=1
            elif sum < target:
                r+=1
            else:
                l+=1
        return res