Leetcode 862 Shortest Subarray with Sum at Least K

发表于 |

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.
If there is no non-empty subarray with sum at least K, return -1.

Example 1:
Input: A = [1], K = 1
Output: 1

Example 2:
Input: A = [1,2], K = 4
Output: -1

Example 3:
Input: A = [2,-1,2], K = 3
Output: 3

Note:

  1. 1 <= A.length <= 50000
  2. -10 ^ 5 <= A[i] <= 10 ^ 5
  3. 1 <= K <= 10 ^ 9

这题思路来源于@lee215大神，我没想到用队列来保存下标，只想到了哪些数可以不考虑（见分析第2步中提到的假设）

分析：

  1. 显然，我们会想到使用dp[i]记录sum(A[:i])，那么这道题就变成了，给定一个数组dp,找到一组i,j，使得dp[j]-dp[i]>=K，且j-i尽量小！
  2. 数据长度达到50000，显然不能使用O(n^2)复杂度的方法，我们得想办法让i,j只走一遍
  3. 用一个简单的示例来分析，设 A = [4,-1,2,3],，K = 5，那么dp = [0,4,3,5,8]，我们从dp数组的第2个数开始分析，（假设来了个-1，那么因为-1比0小，后面任意一个数val如若满足val-0>K,那么val+1也一定大于K，且-1所在的位置i显然能获得更优解，所以0这个位置就失去了意义），现在考虑示例，来了个4，我们发现4-0小于5，我们怎么对4进行处理呢，因为考虑到之后或许会出现一个足够大的数，比如9，那么4相对于0是更优的，但也有可能只来一个8，那么4就没作用了，所以先暂且保留观察。等到来了一个5以上的数，我们依次对保留的数（目前是0，4）进行判断得最优解。
  4. 接下来来了个3，那么根据上面提到的论点，4将会被舍弃，但3比0要大，故此时0，3保留。
  5. 然后来了个5，5-0>=5，故找到一组i,j，记录下来，然后判断 5-3>=5 ?如若确实大于，即再次找到一组i,j，若小于，则5保留（考虑到之后或许来了个10），依次类推

思路：

  1. 建立一个队列记录保留数字，初始为0
  2. 依次对dp中的数进行分析，如果dp[i] - dp[Q[0]] >= K，则记录一次i,j
  3. 如果dp[i] < dp[Q[-1]]，则舍弃Q[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import Queue
class Solution(object):
    def shortestSubarray(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        # 如若有比K大的数，则直接返回1
        if max(A) >= K: return 1

        # 记录和，dp[i] = sum(A[:i])
        dp = [0] * (len(A)+1)
        for i in range(1,len(dp)):
            dp[i] = dp[i-1] + A[i-1]

        res = float('inf')
        # 初始化队列
        Q = Queue.deque([0])
        for i in range(1,len(dp)):
        	# 思路中第2步
            while Q and dp[i]-dp[Q[0]] >= K:
                res = min(res,i-Q.popleft())
            # 思路中第3步
            while Q and dp[i]<dp[Q[-1]]:
                Q.pop()
            Q.append(i) 
        return [res,-1][res==float('inf')]

O(n) time, O(n) space
93 / 93 test cases passed.
difficulty: hard
Runtime: 693 ms