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.
