# Python leetcode862. 和至少为 K 的最短子数组 详解

###### 如果没有和至少为 K 的非空子数组，返回 -1 。
```            ```
示例

1

：

=

[

1

]

,

K

=

1

1

2

：

=

[

1

,

2

]

,

K

=

4

-

1

3

：

=

[

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

```
```

deque模块效率略高，500个元素大概快60ms.

QQ号联系： 360901061

【本文对您有帮助就好】