【算法题】:和为N的连续正数序列
- 输入一个正数,输出所有和为N的连续正数序列
- 例如:输入15
- 结果:[[1,2,3,4,5],[4,5,6],[7,8]]
方法一:双指针法
思路简述:
- 用两个指针 start 和 end,初始都指向1
- 计算区间[start, end]的和 sum
- 如果 sum == N,记录序列,start++缩小区间
- 如果 sum < N,end++扩大区间
- 如果 sum > N,start++缩小区间
- 直到 start 超过 N/2(因为连续正数最少两个,最大起点不会超过 N/2)
示例代码
function findContinuousSequence(N) {let result = [];let start = 1, end = 1;let sum = 0;while (start <= Math.floor(N / 2)) {if (sum < N) {sum += end;end++;} else if (sum > N) {sum -= start;start++;} else {// sum === Nlet seq = [];for (let i = start; i < end; i++) {seq.push(i);}result.push(seq);// 移动start继续找sum -= start;start++;}}return result;
}// 测试
console.log(findContinuousSequence(15));
// 输出:[[1,2,3,4,5],[4,5,6],[7,8]]
方法二:
思路:
- 从N开始计算连续M个的正数序列和:total = N+(N+1)+…+(N+M-1) = (N+(N+M-1))*M/2
function createArr(n, len) {let arr = new Array(len).fill(null);let temp = [];arr[0] = n;arr = arr.map((item, index) => {if (item === null) {item = temp[index - 1] + 1;}temp.push(item);return item;});return arr;
}function fn(count) {let result = [];// => 求出中间值let middle = Math.ceil(count / 2);// 1 从1开始累加for (let i = 1; i <= middle; i++) {// 控制累加多少次for (let j = 2;; j++) {// 求出累加多次的和let total = (i + (i + j - 1)) * (j / 2);if (total > count) {break;} else if (total === count) {result.push(createArr(i, j));break;}}}return result;
}// 测试
console.log(fn(15));
// 结果:[[1,2,3,4,5],[4,5,6],[7,8]]