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

本问题对应的 leetcode 原文链接:剑指 Offer 57 – II. 和为s的连续正数序列
对应打卡内容:剑指 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)

发表回复

后才能评论