leetcode 面试题57 - II. 和为s的连续正数序列【滑动窗口】

118 阅读 0 评论 78 点赞

我是靠谱客的博主无私香菇，这篇文章主要介绍leetcode 面试题57 - II. 和为s的连续正数序列【滑动窗口】，现在分享给大家，希望可以做个参考。

题目链接：面试题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]]

程序说明：

设置成左闭右开区间会比较好做，sum小于target右端点加1，sum大于target左端点加1，sum等于target记录答案(答案区间是左闭右开的)，然后左端点加1。

注意最后返回的是二维数组，可以用toArray()带参数的方法。（对Java选手极不友好…）

代码如下：

复制代码

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
class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        int i = 1, j = 1, sum = 0;
        while(i <= target / 2) {
            if(sum < target) {
                sum += j;
                j++;
            }
            else if(sum > target) {
                sum -= i;
                i++;
            }
            else {
                int[] a = new int[j - i];
                int len = 0;
                for(int k = i; k < j; k++)
                    a[len++] = k;
                res.add(a);
                sum -= i;
                i++;
            }
        }
        return res.toArray(new int[0][]);
    }
}