Leetcode:滑动窗口 --对于连续的正整数序列题解

69 阅读 0 评论 46 点赞

我是靠谱客的博主开朗哑铃，最近开发中收集的这篇文章主要介绍Leetcode:滑动窗口 --对于连续的正整数序列题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Sliding window

滑动窗口

滑动窗口作为对数组类算法题中惯用的方法,通常能通过对设置好的"窗口"移动可观察得到候选结果,当窗口从左临界点移动到右临界点时,即可得出最优结果.

举例:
剑指Offer 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]]

限制：

1 <= target <= 10^5

对于我来说,这道题上手的第一反应就是公差为1的等差数列求和…
那么利用这一点,因为是一个[1,2,3…n]的连续正整数序列,应用滑动窗口的思想,便可把窗口的范围设置出来,即:

若为奇数的话: 则窗口的右临界点为 target/2 +1
若为偶数的话: 则窗口的右临界点为 target/2

通常情况下,滑动窗口改变的点是左临界点即作为初始点,向右移动
一般可以将滑动窗口作为一个左闭右开的区间.

滑动窗口的重要性质是：窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n)O(n)。如果左右边界向左移动的话，这叫做“回溯”，算法的时间复杂度就可能不止 O(n)O(n)。

对于此题:由于输入的值是滑动窗口需得出的结果,则可以把target当成滑动窗口中所有数的和. 当滑动窗口的右边界(设为right)向右移动一个位置,那么下一个窗口内的序列和就要加上right+1.同样的道理左边界向右移动,则要减去未移动前的左边界的值.

为了防止回溯,滑动窗口的左边界和右边界设定只能向右移动即向右临界点移动.从而保证时间复杂度为O(n)

对于数组,我们要考虑的是什么时候"扩大"窗口和"缩小窗口".

以示例2为例:

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

"扩大窗口"即窗口内的和小于target时,就要考虑左边界或右边界的移动,但是因为之前提到为了防止回溯的原因,只能使有边界向右移动
同理,当窗口内的和小于target时,让左边界向右移动
target==(窗口的和)时即可返回一个序列(此时的序列是length最长的序列) 随着左边界的右移为了保证之后窗口内的和==target 想必会减少窗口内数字的数量

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1;  // 滑动左窗口
        int j = 1;  // 滑动右窗口
        int sum = 0;
        List<int[]> ans = new ArrayList<>();
        while(i <= target/2){
            if(sum < target){
                sum += j;
                j++;
            }
            if(sum > target){
                sum -= i;
                i++;
            }
            if(sum == target){
                int[] arr = new int[j-i];
                int m = 0;
                for(int k = i; k < j; k++){
                    arr[m++] = k;
                }
                m = 0;
                ans.add(arr);
                // sum -= i;
                // i++;
		        sum -= 2*i + 1;
                i += 2;
            }
        }

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