- 题目描述
输入一个正整数 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
- 解法一：双指针
仔细想一想这其实是个滑动窗口的题，和为target的list是连续的，因此我们可以想到可以用一个指针p1从左往右遍历一遍数组，然后用一个p2，从p1往后遍历。什么时候p2停止呢，就是当p1, p2围成的数组的和刚好等于target的时候，此时则说明p2再往后遍历，那么p1，p2指针围成的数组的和则会大于target了。此时，左指针p1应该往右移，此时才能继续找和到target的序列，此时p2则又往右继续遍历，直到找到下一个和等于target的序列或者大于target的序列，此时p1又往右移动。
指针结束移动的条件是当p1越过target的中值，为什么是中值的呢？可以想象其实大于中值后，两个及两个元素以上的序列和肯定大于target了。
直接上代码：
def findContinuousSequence(self, target): p1, p2 = 1, 2 alist = [] currentSum = p1 + p2 while p1 <= (target +1) //2: if currentSum == target: alist.append([i for i in range(p1, p2+1)]) currentSum -= p1 p1 += 1 elif currentSum < target: p2 += 1 currentSum += p2 elif currentSum > target: currentSum -= p1 p1 += 1 return alist
- 解法二：求根法
代码：
class Solution: def findContinuousSequence(self, target: int): # 创建输出列表 res = [] # y不能超过target的中值,即y<=target//2 + 1,range函数左开右闭,所以这里是+2 for y in range(1,target//2 + 2): # 应用我们的求根公式 x = (1/4 + y**2 + y - 2 * target) ** (1/2) + 0.5 # 我们要确保x不能是复数，且x必须是整数 if type(x) != complex and x - int(x) == 0: res.append(list(range(int(x),y+1))) return res
我觉得求根法和间隔法在面试的时候不一定想得到，就算想到了在面试的时候也不一定推得对。
- 解法三：间隔法
代码：
#数学求解+间隔计算： def findContinuousSequence(self, target: int) -> List[List[int]]: i, res = 1, [] while i * (i + 1) / 2 < target: if (target - i * (i+1)/2) % (i + 1) == 0: x = int((target - i * (i+1)/2) // (i + 1)) res.append(list(range(x, x+i+1))) i += 1 return res[::-1]