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

100 阅读 0 评论 66 点赞

我是靠谱客的博主瘦瘦未来，这篇文章主要介绍Leetcode面试题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]]

AC代码:滑动窗口算法

复制代码

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
class Solution {
    public int[][] findContinuousSequence(int target) {
        int sum = 0;
        int left = 1;
        int right = 1;
        List<int[]> lists = new ArrayList<>();

        while(left <= target / 2){
            if(sum == target){
                int[] tmp = new int[right - left];
                for(int i=left;i!=right;++i){
                    tmp[i - left] = i;
                }
                lists.add(tmp);
                sum -= left;
                ++left;
            }
            else if(sum > target){
                sum -= left;
                ++left;
            }
            else{
                sum += right;
                ++right;
            }
        }
        return lists.toArray(new int[lists.size()][]);
    }
}