算法/编程练习：寻找和至少为K的最短子数组

本文主要是介绍算法/编程练习：寻找和至少为K的最短子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

寻找和至少为K的最短子数组

1. 题目

题目来自LeetCode:
https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/

题目：

返回非空列表A的最短的非空连续子数组的长度，该子数组的和至少为K。
如果没有和至少为K的非空子数组，返回 -1 。
例如，
input: A = [1, 2],  K = 4
output:  -1input: A = [2, -1, 2],  K = 3
output:  3

2. 思路（来自官方题解）：

题目转换：
记P存放A的累计求和列表(P[x+1] = P[x] + A[x])
找到在满足P[y]-P[x] >= K情况下使y-x最小的y-x解答思路：全局最优解：最终需要的结果特定最优解x：当y固定时，满足条件的最大x特定最优解x满足规律：当y固定的时候，若x2 > x1且P[x2] <= P[x1](相当于A[x1]和A[x2]之间有负数)则x1必然不是y对应的特定最优解，因为若x1可行，则x2也可行且比x1更优因此(在x递增的方向)寻找y的特定最优解时，若x1 < x2且P[x1] >= P[x2]，则x1可直接删除当x为多个y的特定最优解时的规律：对于任何y2 > y1，若x同时是y1和y2对应的特定最优解，则y1-x一定优于y2-x因此在y递增的方向寻找全局最优解时，若x是y的特定最优解，则后续不用再考虑x(因为y递增)用一个双端列队deq存放可能是特定最优解的下标x，然后求解分两个步骤，对A的每个元素A[y]：1) 首先y固定，删除deq中所有x < y且P[x] > P[y]的x2) 对deq中的从小到大的每个下标x，若x为y的特定最优解，则将其删除

3. Python代码：

# -*- coding: utf-8 -*-import collectionsdef SumKShortestSublist(A, K):if not isinstance(A, list) or len(A) < 1:print('A须为非空列表！')return -1N = len(A)P = [0] # 存放累计和列表for a in A:P.append(P[-1] + a)best_ans = N+1 # best_ans记录全局最优解，N+1 is impossible    deq = collections.deque() # 双端列队deq存放可能是特定最优解的下标xfor y, P_y in enumerate(P):# 当y固定时，删除d中所有x < y且P[x] > P[y]的xwhile deq and P_y <= P[deq[-1]]:deq.pop()# 若x是y的特定最优解，则后续不用再考虑xwhile deq and P_y - P[deq[0]] >= K:best_ans = min(best_ans, y-deq.popleft())deq.append(y)return best_ans if best_ans < N+1 else -1if __name__ == '__main__':A = [1]K = 1print(SumKShortestSublist(A, K))A = [1, 2]K = 5print(SumKShortestSublist(A, K))    A = [2, 1, 2]K = 3print(SumKShortestSublist(A, K))A = [2, -1, 2]K = 3print(SumKShortestSublist(A, K))A = [84, -37, 32, 40, 95]K = 167print(SumKShortestSublist(A, K))