专栏首页小浩算法漫画:滑动窗口入门题目,没有之一

漫画:滑动窗口入门题目,没有之一

今天是小浩算法“365刷题计划”第83天 。昨天写了一篇感悟,没想到那么受欢迎。几百人转发,好几千人阅读,虚荣心得到了极大的满足。今天继续为大家分享一道经典面试题目。

01

PART

和为s的连续正数序列

咕咕咕...一道很简单的题目~

题目:输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例 1:

输入:target = 9

输出:[[2,3,4],[4,5]]

示例 2:

输入:target = 15

输出:[[1,2,3,4,5],[4,5,6],[7,8]]

02

PART

题目分析

特别提醒:这两天有人问我,说浩哥,为什么看了你那么多题解,但是我一旦上机写,便啥都不记得了。这个我想说。。。你真牛掰。普通人应该都做不到看看题解,就能真的掌握一个题目(不信你看书学学KMP,再试试看能不能一次写出来)。题解只是给你提供一个思路,真正的提高,取决于coding的过程。大量的练习,忍受难受的过程,才能真正的进步!

这个题目比较简单,典型的一道滑动窗口的题目。如果对滑动窗口陌生,可以先看下下面的题解:

漫画:滑动窗口 第一讲(滑动窗口最大值)

漫画:滑动窗口 第二讲(无重复字符的最长子串)

漫画:滑动窗口 第三讲(找到字符串中所有字母异位词)

假若我们输入的 target 为 9,大脑中应该有下面这么个玩意:

然后我们通过左右指针来维护一个滑动窗口,同时计算窗口内的值是否是目标值:

如果窗口的值过小,我们就移动右边界。

如果窗口的值过大,我们就移动左边界。

剩下的就是反复上面的操作就可以了。到这里分析过程看似结束了。但是我们可以观察出一丢丢规律,用来优化我们的算法。对于任意一个正整数,总是小于它的中值与中值+1的和。为了让大家直观,用下图举例:

比如这里的100,就一定小于50+51,换成其他数也一样。换句话说,一旦窗口左边界超过中值,窗口内的和一定会大于 target

根据分析,得到题解:(好久没给Go语言的示例了,刻意把代码写的比较简单,没有用啥骚操作哈)

//go
func findContinuousSequence(target int) [][]int {
    result := make([][]int, 0)
    i := 1
    j := 1
    win := 0
    arr := make([]int, target)
    for i := range arr {
        arr[i] = i + 1
    }
    for i <= target/2 {
        if win < target {
            win += j
            j++
        } else if win > target {
            win -= i
            i++
        }  else {
            result = append(result, arr[i-1:j-1])
            win -= i
            i++
        }
    }
    return result
}

同时也给一个java版本的:

//java
class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        int i = 1; 
        int j = 1; 
        int win = 0; 
        while (i <= target / 2) {
            if (win < target) {
                win += j;
                j++;
            } else if (win > target) {
                win -= i;
                i++;
            } else {
                int[] arr = new int[j-i];
                for (int k = i; k < j; k++) {
                    arr[k-i] = k;
                }
                res.add(arr);
                win -= i;
                i++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。

03

PART

继续优化

到这里你以为这个题目就结束了吗?...哈哈哈哈哈...其实真就结束了~囧!o(╯□╰)o

本题我使用滑动窗口进行求解,是期望给出一种通用解法。有很多基础差的同学,并不能每道题目都玩出来骚操作。但是本题除了常规的滑动窗口之外,其实还有数学法,递推法等多种解题思路。这里给出数学法的提示:等差数列求和公式,希望大家下去自行思考一番,评论区留下你的想法!咱们明天见!

今天的题目到这里就结束了

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer 03:二维数组中的查找

    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

    程序员小浩
  • 《剑指offer》第11天:矩形覆盖

    我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

    程序员小浩
  • 万字长文!位运算面试看这篇就够了!

    祝大家五一快乐。今天是小浩算法 “365刷题计划” 位运算超长 - 整合篇。估计五一期间,大家也没有什么心思好好做题。所以我就把之前已经出过的位运算系列,进行了...

    程序员小浩
  • hdu portal(经典)

    这是一道好题,让我又学了一个新的知识,离线算法+并查集 题意:先给出图,求存在多少路径使得花费T小于L,T的定义是u,v亮点的所有路径的最大边的最小值 (Unf...

    用户1624346
  • P2015 二叉苹果树

    题目描述 有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点) 这棵树共有N个结点(叶子点或者树枝分叉点),编号为1-N,树根编号一定是1...

    attack
  • 进程同步(四)—— 消息队列

    Aichen
  • BZOJ2216: [Poi2011]Lightning Conductor(DP 决策单调性)

    首先把给出的式子移项,我们要求的$P_i = max(a_j + \sqrt{|i - j|}) - a_i$。

    attack
  • codevs 1664 清凉冷水

    1664 清凉冷水 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description      ...

    attack
  • 2833 奇怪的梦境 未AC

    2833 奇怪的梦境 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description Aide...

    attack
  • 2833 奇怪的梦境

    题目描述 Description Aiden陷入了一个奇怪的梦境:他被困在一个小房子中,墙上有很多按钮,还有一个屏幕,上面显示了一些信息。屏幕上说,要将所有按钮...

    attack

扫码关注云+社区

领取腾讯云代金券