【LeetCode】面试题57 - II. 和为s的连续正数序列 LCOF2020年3月6日

122 阅读 0 评论 81 点赞

我是靠谱客的博主专注蚂蚁，这篇文章主要介绍【LeetCode】面试题57 - II. 和为s的连续正数序列 LCOF2020年3月6日，现在分享给大家，希望可以做个参考。

题目

题目传送门：传送门（点击此处）
在这里插入图片描述

题解

思路

其实有数学方法，我实在是不太会。。。
于是我选择了滑动窗口来解决这个问题

怎么用滑动窗口

在这里插入图片描述

主要是解决滑动窗口移动得问题，左右端点如何移动

如果 i-j 的和值相加大于 target 得时候，左边界向右移动
如果 i-j 的和值相加小于 target 得时候，右边界向右移动
如果 i-j 的和值相加等于 target 得时候，左边界向右移动，这时状态又回到了小于 target 的时候

在这里插入图片描述

code

复制代码

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
class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1; // 滑动窗口的左边界
        int j = 1; // 滑动窗口的右边界
        int sum = 0; // 滑动窗口中数字的和
        List<int[]> resList = new ArrayList<>();
        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;
                }
                // 左边界向右移动
                resList.add(arr);
                sum -= i;
                i++;
            }
        }
        return resList.toArray(new int[resList.size()][]);
    }
}