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

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條評論
主站蜘蛛池模板: 五月激情久久 | 久久久久久久国产高清 | 女人十六毛片 | 欧美激情精品久久久久久大尺度 | 人人鲁免费播放视频人人香蕉 | 九九热视频免费 | 毛片a级放荡的护士hd | 羞羞的视频在线观看 | 亚洲在线久久 | 国产99青草全福视在线 | 一本色道久久综合亚洲精品 | 波多野结衣久久一区二区 | www九色| 久青草国产在线视频亚瑟影视 | 波多野结衣三区 | 国产成人精品午夜在线播放 | 亚洲欧洲一二三区机械有限公司 | 日韩中文字幕精品免费一区 | 国产精品 视频一区 二区三区 | 欧美成人看片一区二区三区 | 国产成人香蕉在线视频fuz | 欧美精品久久久久久久影视 | 综合一区 | 四虎国产精品4hu永久 | 色一情一欲一爱一乱 | 青青热久久国产久精品秒播 | 欧美操操操 | 看全色黄大色黄大片 视 | 欧美精品中文 | 香蕉视频精品 | 国产精品免费看久久久麻豆 | 可以免费观看欧美一级毛片 | 欧美日韩精品 | 中文字幕最新中文字幕中文字幕 | 国产国语对白一级毛片 | 激情综合婷婷 | 91精品成人福利在线播放 | 成人国产精品一区二区网站 | 久久线看观看精品香蕉国产 | 免费不卡中文字幕在线 | 99久久中文字幕伊人 |