V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
gbin
V2EX  ›  算法

2018026 今日算法

  •  1
     
  •   gbin · 2018-03-26 09:06:04 +08:00 via Android · 3723 次点击
    这是一个创建于 2194 天前的主题,其中的信息可能已经有所发展或是发生改变。
    给定一个有序数组 s 和一个数 t,求数组中连续元素的和等于所给数的子数组。


    s = [1,2,3,4,5,6,7]
    t = 12

    输出
    [3,4,5]
    22 条回复    2018-04-01 10:34:18 +08:00
    lhx2008
        1
    lhx2008  
       2018-03-26 09:19:19 +08:00 via Android
    和 two-sum 排序版 解法一样,两个指针小了左边右移,大了右边左移就行
    flyingpot
        2
    flyingpot  
       2018-03-26 09:19:19 +08:00 via iPhone
    同向双指针?
    gbin
        3
    gbin  
    OP
       2018-03-26 09:20:27 +08:00 via Android
    @lhx2008 老哥手法老练👍
    binux
        4
    binux  
       2018-03-26 09:22:17 +08:00
    不管怎么做都是 O(n) 的,对这种算法毫无兴趣。
    binux
        5
    binux  
       2018-03-26 09:23:52 +08:00
    @binux 哦,确实可以 O(logn) 的。不过还是挺无趣的。
    gbin
        6
    gbin  
    OP
       2018-03-26 09:23:55 +08:00 via Android
    @binux 允许我大胆猜测一下,你是算法岗?
    muziki
        7
    muziki  
       2018-03-26 09:27:45 +08:00
    @gbin 这位是 python 巨佬
    binux
        8
    binux  
       2018-03-26 09:28:31 +08:00
    @gbin 超偏门的算法。
    hanzichi
        9
    hanzichi  
       2018-03-26 09:44:04 +08:00
    @binux O(logn) 能解?求指导
    binux
        10
    binux  
       2018-03-26 09:50:41 +08:00
    @hanzichi 反正数组有序,和它左右两边相加也是有序的,二分就好了嘛。
    binux
        11
    binux  
       2018-03-26 09:52:08 +08:00
    @hanzichi 不过经你这么一说,好像没有规定连续的个数啊。。尴尬
    mengyaoss77
        12
    mengyaoss77  
       2018-03-26 09:58:02 +08:00
    是滑动窗口吗
    binux
        13
    binux  
       2018-03-26 10:00:45 +08:00
    我被题目误导了,因为你这输出不唯一啊,但是没要求给出"所有"子数组啊
    stevenbipt
        14
    stevenbipt  
       2018-03-26 10:27:06 +08:00
    瑟瑟发抖的萌新看着前面一群大佬在前排交流 (っ °Д °;)っ
    qwsqwa
        15
    qwsqwa  
       2018-03-26 10:36:56 +08:00 via Android
    这道题基本算法就是双指针,复杂度 O(n),但没有用到有序这个条件。所以感觉可能会有时间复杂度更低的算法。
    但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和,则必须遍历整个数组。
    pwrliang
        16
    pwrliang  
       2018-03-26 11:14:10 +08:00
    @lhx2008 您好,那个 sorted 2 sum 我做出来了,您能说下这个 n-sum 问题怎么解吗,谢谢?
    Justin13
        17
    Justin13  
       2018-03-26 11:20:21 +08:00 via Android
    双指针,两头开始,求指针间数字的和,大了右边指针左移,小了双指针右移,对不对?
    vegito2002
        18
    vegito2002  
       2018-03-26 11:30:28 +08:00 via iPad
    如果没有负数的话, 两个指针同时从左边走的滑动窗口应该可以;

    各种楼上说的两头指针从左右两头走的方法没有理解具体怎么做。
    akio
        19
    akio  
       2018-03-26 11:37:56 +08:00
    没有说是几个数呀,应该是滑动窗口吧
    lhx2008
        20
    lhx2008  
       2018-03-26 11:54:59 +08:00 via Android
    @pwrliang 我当时想的是,a,b 指针,sum 值,b 先扫到尾部,不断累加 sum 值,再右移 a 或者左移 b,相应加减 sum。但是实际上的话,这样写会有点 bug,应该是个滑动窗口问题更加合适。
    glasslion
        21
    glasslion  
       2018-03-26 14:33:09 +08:00
    @vegito2002
    我想到的也是一头一尾两指针同事往右移, 先移尾,超过了则移头, 如此反复
    find
        22
    find  
       2018-04-01 10:34:18 +08:00 via iPhone
    target/2 然后从中间往两边走
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1269 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 17:51 · PVG 01:51 · LAX 10:51 · JFK 13:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.