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

剑指offer最优解免费

本问题对应的 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;
};

剑指offer题解