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

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條評論
主站蜘蛛池模板: 怡红院免费va男人的天堂 | 日本中文一二区有码在线观看 | 国产亚洲精品成人一区看片 | 欧美视频www | 国产深夜福利视频观看 | 免费视频网站一级人爱视频 | 日韩在线看片中文字幕不卡 | 91啦视频在线观看 | 综合欧美日韩 | 色综合天天综合网站中国 | 日韩精品综合 | 欧美一区二区在线观看视频 | 亚洲99在线的 | 亚洲精品国产福利一区二区三区 | 精品国产日韩一区三区 | 美女被羞羞的网站 | 国产青草视频免费观看97 | 亚洲国产精 | 精品国精品国产自在久国产不卡 | 久久精品国产亚洲香蕉 | 欧美日韩高清在线观看 | 日日摸夜夜添夜夜添一区二区 | 欧美国产日韩在线 | 色伊人久久 | 天天操夜夜夜 | 四虎最新网址入口 | 四虎.com| 96精品国产高清在线看入口 | 精品久久久99大香线蕉 | 亚洲国产美女精品久久久久 | 亚洲国产精品久久久久久 | 黄色α片 | 天天操夜夜摸 | 国产国语高清在线视频二区 | 四虎免费永久网站入口 | 黄色a毛片 | 亚洲综合性图 | 麻豆国产在线观看一区二区 | 免费观看日本污污ww网站精选 | 国产精品久久久久久久久福利 | 香蕉视频在线视频 |