leetcode - 面试题57 - II. 和为s的连续正数序列

95 阅读 0 评论 63 点赞

我是靠谱客的博主隐形绿茶，这篇文章主要介绍leetcode - 面试题57 - II. 和为s的连续正数序列，现在分享给大家，希望可以做个参考。

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

复制代码

1
2
输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

复制代码

1
2
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

1 <= target <= 10^5

题解思路

可以采用枚举+暴力的方式来得到所有满足条件的数组，枚举变量值的上限为target/2取整;在这个枚举的基础上，去比遍历这个值大的所有值，累加起来看是否满足条件。看到题解中有使用滑动窗口的方法来做，发现非常的简洁。即参考的题解做法：

作者：nettee
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/shi-yao-shi-hua-dong-chuang-kou-yi-ji-ru-he-yong-h/
来源：力扣（LeetCode）

复制代码 //数组首字母下标的上限是(target-1)/2
1
2
   //数组首字母下标的上限是(target-1)/2

复制代码

1
2
3
4
5
6
    //可以看成是滑动窗口
    //当窗口的和小于target时候，窗口应该扩大，所以窗口右边界要向右边移动
    //当窗口的和大于target时候，窗口应该缩小，所以窗口的左边界要向右边移动
    //当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)[i,j)，那么我们已经找到了一个 ii 开头的序列，也是唯一一个 ii 开头的序列，接下来需要找 i+1i+1 开头的序列，所以窗口的左边界要向右移动
    //窗口是左闭右开

在这里插入图片描述

复制代码

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

/**
 * @Author liuhaoqi
 * @Date 2020/3/6 11:30
 * @Version 1.0
 */
public class leetcode_57 {
    public int[][] findContinuousSequence(int target) {
        //用枚举+暴力方法做一遍
        List<int[]> list = new ArrayList<>();
        //数组首字母下标的上限是(target-1)/2
        //可以看成是滑动窗口
        //当窗口的和小于target时候，窗口应该扩大，所以窗口右边界要向右边移动
        //当窗口的和大于target时候，窗口应该缩小，所以窗口的左边界要向右边移动
        //当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)[i,j)，那么我们已经找到了一个 ii 开头的序列，也是唯一一个 ii 开头的序列，接下来需要找 i+1i+1 开头的序列，所以窗口的左边界要向右移动
        //窗口是左闭右开
        int i=1;
        int j=1;
        int sum=0;
        while (i<=target/2) {
            if (sum < target) {
                //窗口要扩大
                sum+=j;
                j++;
            } else if (sum > target) {
                //窗口要缩小
                sum -= i;
                i++;
            } else {
                //找到了这组数
                int[] arr=new int[j-i];
                for (int k = i; k <j ; k++) {
                    arr[k - i] = k;
                }
                list.add(arr);
                //左边界向右移动，找下一组数
                sum-=i;
                sum=sum-i-1;
                i+=2;
            }
        }
    return list.toArray(new int[list.size()][]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

/**
 * @Author liuhaoqi
 * @Date 2020/3/6 11:30
 * @Version 1.0
 */
public class leetcode_57 {
    public int[][] findContinuousSequence(int target) {
        //用枚举+暴力方法做一遍
        List<int[]> list = new ArrayList<>();
        //数组首字母下标的上限是(target-1)/2
        //可以看成是滑动窗口
        //当窗口的和小于target时候，窗口应该扩大，所以窗口右边界要向右边移动
        //当窗口的和大于target时候，窗口应该缩小，所以窗口的左边界要向右边移动
        //当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)[i,j)，那么我们已经找到了一个 ii 开头的序列，也是唯一一个 ii 开头的序列，接下来需要找 i+1i+1 开头的序列，所以窗口的左边界要向右移动
        //窗口是左闭右开
        int i=1;
        int j=1;
        int sum=0;
        while (i<=target/2) {
            if (sum < target) {
                //窗口要扩大
                sum+=j;
                j++;
            } else if (sum > target) {
                //窗口要缩小
                sum -= i;
                i++;
            } else {
                //找到了这组数
                int[] arr=new int[j-i];
                for (int k = i; k <j ; k++) {
                    arr[k - i] = k;
                }
                list.add(arr);
                //左边界向右移动，找下一组数
                sum-=i;
                sum=sum-i-1;
                i+=2;
            }
        }
    return list.toArray(new int[list.size()][]);
    }
}