leetcode【每日一题】和为s的连续正数序列 Java题干想法Java代码更快的办法

87 阅读 0 评论 58 点赞

我是靠谱客的博主鲜艳河马，这篇文章主要介绍leetcode【每日一题】和为s的连续正数序列 Java题干想法Java代码更快的办法，现在分享给大家，希望可以做个参考。

题干

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

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

复制代码

1
2
3
4
5
示例 1：

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

复制代码

1
2
3
4
5
示例 2：

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

想法

滑动窗口
左右指针l，r
判断从左窗口到右的sum
大于target说明太大了左指针右移
小于target说明太小了那么右指针右移

需要说明的是窗口左闭右开

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
28
29
30
31
32
class Solution {
    public int[][] findContinuousSequence(int target) {
        int l=1;
        int r=1;
        int sum=0;
        List<int[]> res = new ArrayList<>();
        while(l<=target/2){
            if(sum<target){
                sum+=r;
                r++;
                
            }
            else if( sum> target){
                sum-=l;
                l++;
            }

            else{
                int [] tem=new int[r-l];
                for(int i=l;i<r;i++){
                    tem[i-l]=i;
                }
                res.add(tem);
                sum-=l;
                l++;

            }
        }
     return res.toArray(new int[res.size()][]);
    }
}

更快的办法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        int i = 1;
        //比如案例：9，9 = 3+4+5 = 3 + (3+1) + (3 + 2), 9 = 4+（4+1），i个数的和是target, 我们要找的条件就是target % i == 0 ，条件成立就从 3 遍历到 5 ，或者从 4 遍历到 5 ；由于我们是从后向前判断的，所以对后把数组反转一下就行了。
        while (target > 0) {
            target -= i++;
            if (target > 0 && target % i == 0) {
                int[] arr = new int[i];
                for (int j = target / i, k = 0; j < target / i + i; j++, k++) {
                    arr[k] = j;
                }
                list.add(arr);
            }
        }
        Collections.reverse(list);
        int[][] res = new int[0][];
        return list.toArray(res);
    }
}