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
#使用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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
