亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Python leetcode862. 和至少為 K 的最短子數組 詳解

系統 1651 0
leetcode862. 和至少為 K 的最短子數組
返回 A 的最短的非空連續子數組的長度,該子數組的和至少為 K 。
如果沒有和至少為 K 的非空子數組,返回 -1 。
            
              示例 
              
                1
              
              :
輸入:A 
              
                =
              
              
                [
              
              
                1
              
              
                ]
              
              
                ,
              
               K 
              
                =
              
              
                1
              
              
輸出:
              
                1
              
              

示例 
              
                2
              
              :
輸入:A 
              
                =
              
              
                [
              
              
                1
              
              
                ,
              
              
                2
              
              
                ]
              
              
                ,
              
               K 
              
                =
              
              
                4
              
              
輸出:
              
                -
              
              
                1
              
              

示例 
              
                3
              
              :
輸入:A 
              
                =
              
              
                [
              
              
                2
              
              
                ,
              
              
                -
              
              
                1
              
              
                ,
              
              
                2
              
              
                ]
              
              
                ,
              
               K 
              
                =
              
              
                3
              
              
輸出:
              
                3
              
            
          

Python leetcode862. 和至少為 K 的最短子數組 詳解_第1張圖片

            
              
                #使用collections.deque模塊版本
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                shortestSubarray
              
              
                (
              
              self
              
                ,
              
               A
              
                ,
              
               K
              
                )
              
              
                :
              
              
                from
              
               collections 
              
                import
              
               deque
        startIndex 
              
                =
              
              
                0
              
              
        totalSum 
              
                =
              
              
                0
              
              
                #總和
              
              
        minLen 
              
                =
              
              
                -
              
              
                1
              
              
        dequeMinus 
              
                =
              
               deque
              
                (
              
              
                )
              
              
                #存儲和為負數區域
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              A
              
                )
              
              
                )
              
              
                :
              
              
            totalSum 
              
                +=
              
               A
              
                [
              
              i
              
                ]
              
              
                if
              
               A
              
                [
              
              i
              
                ]
              
              
                <
              
              
                0
              
              
                :
              
              
                minusRangeSum 
              
                =
              
               A
              
                [
              
              i
              
                ]
              
              
                n 
              
                =
              
               i
                m 
              
                =
              
               i
                
              
                while
              
               minusRangeSum 
              
                <
              
              
                0
              
              
                and
              
               n 
              
                >=
              
               startIndex
              
                :
              
              
                    n 
              
                -=
              
              
                1
              
              
                    minusRangeSum 
              
                +=
              
               A
              
                [
              
              n
              
                ]
              
              
                n 
              
                +=
              
              
                1
              
              
                while
              
               n 
              
                <=
              
               startIndex 
              
                and
              
               startIndex 
              
                <=
              
               i
              
                :
              
              
                    totalSum 
              
                -=
              
               A
              
                [
              
              startIndex
              
                ]
              
              
                    startIndex 
              
                +=
              
              
                1
              
              
                while
              
              
                len
              
              
                (
              
              dequeMinus
              
                )
              
              
                >
              
              
                0
              
              
                and
              
               n 
              
                <=
              
               dequeMinus
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                [
              
              
                0
              
              
                ]
              
              
                :
              
              
                    dequeMinus
              
                .
              
              pop
              
                (
              
              
                )
              
              
                dequeMinus
              
                .
              
              append
              
                (
              
              
                (
              
              n
              
                ,
              
              m
              
                )
              
              
                )
              
              
                while
              
               totalSum 
              
                >=
              
               K
              
                :
              
              
                if
              
               minLen 
              
                ==
              
              
                -
              
              
                1
              
              
                :
              
              
                    minLen 
              
                =
              
               i 
              
                -
              
               startIndex 
              
                +
              
              
                1
              
              
                else
              
              
                :
              
              
                    minLen 
              
                =
              
              
                min
              
              
                (
              
              minLen
              
                ,
              
               i 
              
                -
              
               startIndex 
              
                +
              
              
                1
              
              
                )
              
              
                totalSum 
              
                -=
              
               A
              
                [
              
              startIndex
              
                ]
              
              
                startIndex 
              
                +=
              
              
                1
              
              
                while
              
              
                len
              
              
                (
              
              dequeMinus
              
                )
              
              
                >
              
              
                0
              
              
                and
              
               startIndex 
              
                >=
              
               dequeMinus
              
                [
              
              
                0
              
              
                ]
              
              
                [
              
              
                0
              
              
                ]
              
              
                :
              
              
                    a
              
                ,
              
              b 
              
                =
              
               dequeMinus
              
                .
              
              popleft
              
                (
              
              
                )
              
              
                while
              
               a 
              
                <=
              
               startIndex 
              
                and
              
               startIndex 
              
                <=
              
               b
              
                :
              
              
                        totalSum 
              
                -=
              
               A
              
                [
              
              startIndex
              
                ]
              
              
                        startIndex 
              
                +=
              
              
                1
              
              
                return
              
               minLen

            
          
            
              
                #使用list版本
              
              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                shortestSubarray
              
              
                (
              
              self
              
                ,
              
               A
              
                ,
              
               K
              
                )
              
              
                :
              
              
       startIndex 
              
                =
              
              
                0
              
              
       totalSum 
              
                =
              
              
                0
              
              
                #總和
              
              
       minLen 
              
                =
              
              
                -
              
              
                1
              
              
       listMinus 
              
                =
              
              
                [
              
              
                ]
              
              
                #存儲和為負數區域
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              A
              
                )
              
              
                )
              
              
                :
              
              
           totalSum 
              
                +=
              
               A
              
                [
              
              i
              
                ]
              
              
                if
              
               A
              
                [
              
              i
              
                ]
              
              
                <
              
              
                0
              
              
                :
              
              
               minusRangeSum 
              
                =
              
               A
              
                [
              
              i
              
                ]
              
              
               n 
              
                =
              
               i
               m 
              
                =
              
               i
               
              
                while
              
               minusRangeSum 
              
                <
              
              
                0
              
              
                and
              
               n 
              
                >=
              
               startIndex
              
                :
              
              
                   n 
              
                -=
              
              
                1
              
              
                   minusRangeSum 
              
                +=
              
               A
              
                [
              
              n
              
                ]
              
              
               n 
              
                +=
              
              
                1
              
              
                while
              
               n 
              
                <=
              
               startIndex 
              
                and
              
               startIndex 
              
                <=
              
               i
              
                :
              
              
                   totalSum 
              
                -=
              
               A
              
                [
              
              startIndex
              
                ]
              
              
                   startIndex 
              
                +=
              
              
                1
              
              
                while
              
              
                len
              
              
                (
              
              listMinus
              
                )
              
              
                >
              
              
                0
              
              
                and
              
               n 
              
                <=
              
               listMinus
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                [
              
              
                0
              
              
                ]
              
              
                :
              
              
                   listMinus
              
                .
              
              pop
              
                (
              
              
                )
              
              
               listMinus
              
                .
              
              append
              
                (
              
              
                (
              
              n
              
                ,
              
              m
              
                )
              
              
                )
              
              
                while
              
               totalSum 
              
                >=
              
               K
              
                :
              
              
                if
              
               minLen 
              
                ==
              
              
                -
              
              
                1
              
              
                :
              
              
                   minLen 
              
                =
              
               i 
              
                -
              
               startIndex 
              
                +
              
              
                1
              
              
                else
              
              
                :
              
              
                   minLen 
              
                =
              
              
                min
              
              
                (
              
              minLen
              
                ,
              
               i 
              
                -
              
               startIndex 
              
                +
              
              
                1
              
              
                )
              
              
               totalSum 
              
                -=
              
               A
              
                [
              
              startIndex
              
                ]
              
              
               startIndex 
              
                +=
              
              
                1
              
              
                while
              
              
                len
              
              
                (
              
              listMinus
              
                )
              
              
                >
              
              
                0
              
              
                and
              
               startIndex 
              
                >=
              
               listMinus
              
                [
              
              
                0
              
              
                ]
              
              
                [
              
              
                0
              
              
                ]
              
              
                :
              
              
                   a
              
                ,
              
               b 
              
                =
              
               listMinus
              
                [
              
              
                0
              
              
                ]
              
              
                del
              
              
                (
              
              listMinus
              
                [
              
              
                0
              
              
                ]
              
              
                )
              
              
                while
              
               a 
              
                <=
              
               startIndex 
              
                and
              
               startIndex 
              
                <=
              
               b
              
                :
              
              
                       totalSum 
              
                -=
              
               A
              
                [
              
              startIndex
              
                ]
              
              
                       startIndex 
              
                +=
              
              
                1
              
              
                return
              
               minLen

            
          

不熟悉collections.deque模塊的,可以先閱讀list版本,差別不大。
deque模塊效率略高,500個元素大概快60ms.


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 美妇乱人伦性 | 亚洲国产高清精品线久久 | 亚洲 中文 欧美 日韩 在线人 | 在线欧美精品国产综合五月 | 亚洲国产系列一区二区三区 | 一区二区三区四区免费视频 | 国产午夜精品一区二区 | 成人免费视频视频在线观看 免费 | 在线 v亚洲 v欧美v 专区 | 久久精品一区二区三区中文字幕 | 综合久久久久综合体桃花网 | 国产18到20岁美女毛片 | 婷婷激情在线视频 | 国产一精品一aⅴ一免费 | 欧美成人香蕉在线观看 | 亚洲欧美日韩国产精品第不页 | 精品久久久久久久一区二区伦理 | 欧美黄色第一页 | 嘿咻成人免费视频欧美激情 | 亚洲精品视频在线观看免费 | 亚色视频在线观看 | 成人 日韩 在线 | 99久热只有精品视频免费看 | 免费一级毛片在线播放不收费 | 久久国产精品高清一区二区三区 | 福利视频影院 | 欧美乱妇高清视频免欢看关 | 久久国产香蕉一区精品 | 国产在线视频h | 日韩成人免费aa在线看 | 香蕉人精品视频多人免费永久视频 | 亚洲国产精品久久日 | 天天操天天摸天天爽 | 99热成人精品热久久66 | 国产精品久久久久久久久久98 | 日日操日日碰 | 亚洲一区二区三区久久 | 台湾一级毛片免费播放 | 国产一区二区三区免费视频 | 成人激情开心网 | 色综合久久久高清综合久久久 |