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

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條評論
主站蜘蛛池模板: 亚洲韩精品欧美一区二区三区 | 337p欧洲日本大胆艺术 | 久久精品美女久久 | 成人综合久久综合 | 奇米在线777在线视频 | 香蕉免费一级视频在线观看 | 亚洲精品一区二区不卡 | 日韩精品成人免费观看 | 四虎伊人| 99热在线免费播放 | 国产精品亚洲专一区二区三区 | 久久机热这里只有精品无需 | 亚洲一区高清 | 老司机午夜免费视频 | 免费亚洲成人 | 精品国产乱码一区二区三区麻豆 | 香蕉视频一级 | 91精品国产高清久久久久 | 成人黄色网址 | 日本黄页网站在线观看 | 视频在线一区二区 | 国产一区二区三区影院 | 婷婷国产天堂久久综合五月 | 亚洲精品爱爱久久 | 中文字幕美日韩在线高清 | 99久久免费国产精品热 | 涩色涩| 97久久精品人人澡人人爽 | 国产精品自在线天天看片 | 四虎影视成人 | 国产精彩视频在线 | 精品欧美日韩一区二区三区 | 国产欧美精品区一区二区三区 | 日日摸夜夜嗷嗷叫日日拍 | 一区二区三区国产 | 欧美精品成人a多人在线观看 | 久久精品免费一区二区视 | 日韩欧美在线综合网高清 | 亚洲国产精品综合久久网络 | 99精品视频免费在线观看 | 亚洲图片综合区另类图片 |