本问题对应的 leetcode 原文链接：剑指 Offer 57 – II. 和为s的连续正数序列
问题描述
输入一个正整数 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
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> res = new ArrayList<>();
int i = 1, j = 1;
int sum = 1;
while(i <= target/2){
if(sum < target){
j++;
sum = sum + j;
} else if(sum > target){
sum = sum - i;
i++;
} else {
int[] temp = new int[j - i + 1];
int index = 0;
for(int k = i; k <= j; k++){
temp[index++] = k;
}
sum = sum - i;
i++;
j++;
sum = sum + j;
res.add(temp);
}
}
return res.toArray(new int[res.size()][]);
}
}
时间复杂度：O(n)
额外空间复杂的：O(1)
Python
class Solution(object):
def findContinuousSequence(self, target):
"""
:type target: int
:rtype: List[List[int]]
"""
res = []
i, j = 1, 1
sum_ = 1
while i <= target // 2:
if sum_ < target:
j += 1
sum_ += j
elif sum_ > target:
sum_ -= i
i += 1
else:
temp = list(range(i, j + 1))
sum_ -= i
i += 1
j += 1
sum_ += j
res.append(temp)
return res
C++
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> res;
int i = 1, j = 1;
int sum = 1;
while (i <= target / 2) {
if (sum < target) {
j++;
sum += j;
} else if (sum > target) {
sum -= i;
i++;
} else {
vector<int> temp(j - i + 1);
int index = 0;
for (int k = i; k <= j; k++) {
temp[index++] = k;
}
sum -= i;
i++;
j++;
sum += j;
res.push_back(temp);
}
}
return res;
}
};
Go
func findContinuousSequence(target int) [][]int {
res := [][]int{}
i, j := 1, 1
sum := 1
for i <= target/2 {
if sum < target {
j++
sum += j
} else if sum > target {
sum -= i
i++
} else {
temp := make([]int, j-i+1)
index := 0
for k := i; k <= j; k++ {
temp[index] = k
index++
}
sum -= i
i++
j++
sum += j
res = append(res, temp)
}
}
return res
}
JS
/**
* @param {number} target
* @return {number[][]}
*/
var findContinuousSequence = function(target) {
let res = [];
let i = 1,
j = 1;
let sum = 1;
while (i <= Math.floor(target / 2)) {
if (sum < target) {
j++;
sum = sum + j;
} else if (sum > target) {
sum = sum - i;
i++;
} else {
let temp = new Array(j - i + 1);
let index = 0;
for (let k = i; k <= j; k++) {
temp[index++] = k;
}
sum = sum - i;
i++;
j++;
sum = sum + j;
res.push(temp);
}
}
return res;
};
shuaidi