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

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條評論
主站蜘蛛池模板: 一级欧美毛片成人免费视频 | 999热在线精品观看全部 | 草的我好爽的网站 | 在线久综合色手机在线播放 | 亚洲激情网址 | 国产四区| 日本色图网站 | 久草综合视频在线 | 久久久受www免费人成 | 亚洲欧美一区二区三区二厂 | 国产日韩一区二区三区 | 久久手机精品视频 | 日韩一区二区三区在线观看 | 国产成人啪一区二区 | 精品福利在线 | 亚洲va天堂va国产va久 | 久久亚洲免费视频 | 国产精品乱码高清在线观看 | 亚洲欧美精品综合中文字幕 | 国产精品久久久久久麻豆一区 | 最新国产精品亚洲 | 国产 欧美 在线 | 在线观看中文字幕一区 | 国内免费在线视频 | 国产成人午夜精品5599 | 久久免费精品视频 | 国产成人综合网亚洲欧美在线 | 国产女主播在线视频 | 一级毛片片 | 亚洲视频在线a视频 | 亚洲欧美日韩国产一区二区精品 | 亚洲国产一成人久久精品 | 狠狠色噜狠狠狠狠色综合久 | 国产麻豆精品高清在线播放 | 欧美一级欧美三级在线观看 | 亚洲一区二区三区中文字幕 | 国产在线欧美日韩一区二区 | 日韩我不卡 | 久久这| 亚洲成人综合在线 | 国产丶欧美丶日韩丶不卡影视 |