力扣题目系列：面试题57 - II. 和为s的连续正数序列

56 阅读 0 评论 37 点赞

我是靠谱客的博主害羞野狼，最近开发中收集的这篇文章主要介绍力扣题目系列：面试题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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的题解

//这个解法空间复杂度很小，但是时间复杂度稍高，因为没有利用规律，仅是使用滑动窗口
class Solution {
    public int[][] findContinuousSequence(int target) {
        int start = 1; //开始点，滑动窗口左边界
        int now = 1; //游标，滑动窗口右边界
        int sum = 0;

        List<int[]> list = new ArrayList<>();

        while(start <= target/2){
            while(sum < target){
                sum += now;
                ++now;
            }
            if(sum == target){ //找到一组
                int[] temp = new int[now - start];
                for (int i = 0; i < temp.length; i++) {
                    temp[i] = start + i;
                }
                list.add(temp); //给result赋值 //start到now
                start++; //start = now; //更新开始点
                now = start; //更新游标
                sum = 0; //重置和
            } else if(sum > target){ //开始点不对
                start++; //start = now; //更新开始点
                now = start; //更新游标
                sum = 0; //重置和
            }
        }

        int[][] res = new int[list.size()][];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

滑动窗口结合数学规律

//若能发现公式xa+x*(x-1)/2=target，x表示每一个一维数组的个数
//时空复杂度大大降低
class Solution {
    public int[][] findContinuousSequence(int target) {
        int[][] array = new int[target/2][];
		int num = 0;
		for (int i = 0,x=2; i < target/2; x++) {
			int ax = target - x*(x-1)/2;
                if(ax <= 0)
			break;
		if(ax%x == 0){
			num++;
			int a = ax/x;
			array[num-1] = new int[x];
			for (int j = 0; j < x; j++) {
				array[num-1][j] = a + j;
			}
		}
		i++;
	}
	int[][] array1 = new int[num][];
	for (int i = num-1,j = 0; i >= 0; i--,j++) {
		array1[j] = array[i];
	}
	return array1;
    }
}