微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 57-2. 和为s的连续正数序列

剑指offer 57-2. 和为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

题解 1

(双指针算法) O(n)

最容易想到的是用两重循环去枚举和为 S 的序列，时间复杂度是 O(n^2) 我们可以使用双指针算法进行优化，用两个指针 i, j 指向当前正在枚举的序列的起点和终点

  1. 当 i \sim j 之间的和小于 S 时， j 指针往后移
  2. 当 i \sim j 之间的和等于 S 时，记录当前序列，加入到答案中
  3. 当 i \sim j 之间的和大于 S 时，i 指针往后移

可以 i 和 j 是单调的，不会走回头路，且当 i 往后移时 j 不会往前移

时间复杂度

i 和 j 最终都从 1 走到 target，时间复杂度为 O(n)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        vector<int> path;
        
        for (int i = 1, j = 1, sum = 0; i < target; i ++ ) {
            while (j < target && sum < target) sum += j, j ++ ;
            if (sum == target) {
                for (int k = i; k < j; k ++ ) path.push_back(k);
                res.push_back(path);
                path.clear();
            }
            sum -= i;
        }

        return res;
    }
};

Java 代码

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        
        for (int i = 1, j = 1, sum = 0; i < target; i ++ ) {
            while (j < target && sum < target) {
                sum += j;
                j ++ ;
            }
            if (sum == target) {
                int[] path = new int[j - i];
                for (int k = i; k < j; k ++ ) {
                    path[k - i] = k;
                }
                res.add(path);
            }
            sum -= i;
        }

        return res.toArray(new int[res.size()][]);
    }
}

Python 代码

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        path = []
        
        i, j, s = 1, 1, 0
        while i < target:
            while j < target and s < target:
                s += j
                j += 1
            if s == target:
                path = list(range(i, j))
                res.append(path[:])
                path.clear()
            s -= i
            i += 1

        return res

题解 2

(回溯)

将每个数作为起点开始找合法方案并记录路径和，如果 sum == target，则将路径加入答案中。

剪枝优化：

  1. 如果和 sum > target 说明不是一个合法方案，直接返回。
  2. 如果当前正在遍历的数和路径中的最后一个数不是相邻的，也不是一个合法方案，直接 break 结束当前搜索分支。

时间复杂度

回溯的时间复杂度一般是指数级别的，由于这道题目合法方案数比较少，可以过。

空间复杂度

O(n)

C++ 代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void dfs(int start, int sum, int target) {
        if (sum > target) return;
        if (start == target) return;
        if (sum == target) {
            res.push_back(path);
            return;
        }

        for (int i = start; i < target; i ++ ) {
            if (path.size() && path.back() + 1 != i) break;
            path.push_back(i);
            dfs(i + 1, sum + i, target);
            path.pop_back();
        }
    }

    vector<vector<int>> findContinuousSequence(int target) {
        dfs(1, 0, target);
        return res;
    }
};

Java 代码

class Solution {
    List<int[]> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    void dfs(int start, int sum, int target) {
        if (sum > target || start == target) {
            return;
        }
        if (sum == target) {
            int[] pathArray = new int[path.size()];
            for (int i = 0; i < path.size(); i ++ ) {
                pathArray[i] = path.get(i);
            }
            res.add(pathArray);
            return;
        }

        for (int i = start; i < target; i ++ ) {
            if (!path.isEmpty() && path.get(path.size() - 1) + 1 != i) {
                break;
            }
            path.add(i);
            dfs(i + 1, sum + i, target);
            path.remove(path.size() - 1);
        }
    }

    int[][] findContinuousSequence(int target) {
        dfs(1, 0, target);
        int[][] result = new int[res.size()][];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}

Python 代码

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        path = []

        def dfs(start, total, target):
            if total > target or start == target:
                return
            if total == target:
                res.append(path[:])
                return

            for i in range(start, target):
                if path and path[-1] + 1 != i:
                    break
                path.append(i)
                dfs(i + 1, total + i, target)
                path.pop()

        dfs(1, 0, target)
        return res

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer