LeetCode 面试题57 - II. 和为s的连续正数序列 LCOF
Table of Contents
一、中文版
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、My answer
import math class Solution: def findContinuousSequence(self, target: int) -> List[List[int]]: # version 1:从 n 往前遍历 res = [] n = math.ceil(target / 2) while n > 0: base = n tempSum = 0 l = [] while base >=1 and tempSum < target: l.append(base) tempSum += base base -= 1 if tempSum == target: res.append(l[::-1]) n = n - 1 return res[::-1]
import math class Solution: def findContinuousSequence(self, target: int) -> List[List[int]]: # version 2:正序遍历 res = [] n = math.ceil(target / 2) i = 1 while i <= n: base = i tempSum = 0 l = [] while tempSum < target: tempSum += base l.append(base) base += 1 if tempSum == target: res.append(l) i = i + 1 return res
import math class Solution: def findContinuousSequence(self, target: int) -> List[List[int]]: # version 3：优雅进阶 res = [] n = math.ceil(target / 2) for i in range(1,n): base = i tempSum = 0 while tempSum < target: tempSum += base base += 1 if tempSum == target: l = [] for x in range(i,base): l.append(x) res.append(l) # 以上四行代码可以改为如下列表解析式 # res.append([x for x in range(i,base)]) return res
import math class Solution: def findContinuousSequence(self, target: int) -> List[List[int]]: # version 3：优雅进阶 res = [] n = math.ceil(target / 2) for i in range(1,n): base = i tempSum = 0 while tempSum < target: tempSum += base base += 1 if tempSum == target: l = [] for x in range(i,base): l.append(x) res.append(l) # 以上四行代码可以改为如下列表解析式 # res.append([x for x in range(i,base)]) return res
import math class Solution: def findContinuousSequence(self, target: int) -> List[List[int]]: # version 4:滑动窗口 i, j = 1, 2 n = math.ceil(target / 2) res = [] while j <= n: tempSum = (i + j) * (j - i + 1) / 2 if tempSum == target: res.append([x for x in range(i, j+1)]) i += 1 j += 1 elif tempSum < target: j += 1 else: i += 1 return res
import math class Solution: def findContinuousSequence(self, target: int) -> List[List[int]]: # version 5: 数学公式 n = math.ceil(target / 2) res = [] for i in range(1,n): if (1 - 4 * (i - i*i - 2 * target)) < 0: continue else: formula = 0.5*((1 - 4 * (i - i*i - 2 * target)) ** 0.5) j1 = int(-(1/2) + formula) # j2 = -(1/2) - formula if j1 > i and ((i + j1) * (j1 - i + 1) - 2 * target) == 0: res.append([x for x in range(i,j1+1)]) # if j2 > i and ((i + j2) * (j2 - i + 1) - 2 * target) == 0: # res.append([x for x in range(i,int(j2)+1)]) return res
三、解题报告
共五个版本，下面一一解释。
首先对于所有版本，第一步都是一样的，那就是只需要从 1 考虑到 n = math.ceil(target / 2)，因为至少有两个数求和 = target，若两个数大于 n，此时加和肯定大于 target。
Version 1：
从 n 开始往前遍历。n 是外层循环，每次减1；base 是内层循环，每次减1。在例子1 中 [[2,3,4],[4,5]]，n 是每个 list 的最后一个（此处是5、4），base 是每个 list 内部依次递减1（此处是4 3 2 和 5 4）
把 list 反序的写法 res[::-1]。
Version 2：
把 Version 1 改为从 0 开始往后遍历即是 Version 2。
Version 3：
Version 2 的优雅进阶版。现在还做不到一次就写出优雅的代码，只能慢慢改进一点是一点。
Version 4：
滑动窗口思想。两个同向指针 i, j ，求 i 到 j 的和，判断是否等于 target，如果比 target 小，则 j 右移，否则 i 右移。
tempSum 利用数学公式求和：n项和公式 = （首项+末项）* 个数 / 2。
Version 5：
其中 i 是滑动窗口左侧值所在位置，j 是滑动窗口右侧值所在位置。根据 n项和公式 = （首项+末项）* 个数 / 2，即 i 对首项 j 对应末项。使 求和公式的结果 = target 即可。本算法直接利用数学通项公式
x=[-b±√(b^2-4ac)]/2a 求解。
if (1 - 4 * (i - i*i - 2 * target)) < 0: 是在限制根号内的内容满足 > 0
求出的两个结果一正一负，因此只需要判断正值即可。
