LeetCode 862. Shortest Subarray with Sum at Least K 解题思路分析

今天做的这道题稍微懂了点脑筋，做完后看了看官方给出的答案，感觉还是不太用以理解，所以还是把自己的思路分享出来。

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=862

解题思路分析：

题目给出了一个int型数组A和一个int数字K，要求在数组A中找到一个最短子数组并且其和大于等于数字K。

鉴于题目在LeetCode总难度排行榜上高居第六位，因此暴力破解法（2层for循环）肯定行不通，大概率会出现Time Limit Exceeded，因此尽量考虑1层循环解决问题（这也是大家常说的时间复杂度为O(n) ）。

大体上考虑到以下几点即可：

1. 因为K为正整数，子数组的首尾若是负数会增加求和负担。所以符合要求的子数组一定是以正数起始（subA[0] > 0），并以正数结束。
2. 同理，如果A数组中连续n个元素之和小于等于0，那么这连续的n个元素也属于求和负担，也不能出现在子数组的开始位置。
3. 循环时考虑使用2个index，一个记录子数组开始位置，一个记录结束位置。起初，开始index与结束index均为0。如果当前index是负数，那么起始index与结束index均相应右移，直到当前位置为正数为止。接下来，只右移结束index，并记录下起始与结束index间数值总和sum。若总和出现负数，同时右移起始与结束index至下一正数坐标位置。重复上述操作，直至出现总和sum大于等于K时，记录下起始与结束index间距离。需要注意的是，这时得到的距离不一定是当前结束index为止的最短距离，因为该大于K的总值是起始index到结束index的数值总和，我们一直在右移结束index，当得到符合条件的解时，应保持结束index的同时尝试右移起始index。例如，数组A为[1，2，99]，K为100，所以，按照我们的解题思路应该是下面的顺序。

// 右移结束index
 起始index=0,结束index=0 // subArray = [1]; sum = 1;
 起始index=0,结束index=1 // subArray = [1, 2] sum = 3;
 起始index=0,结束index=2 // subArray = [1, 2, 99] sum = 102,符合条件
 // 右移起始index
 起始index=1,结束index=2 // subArray = [2, 99] sum = 101,符合条件
 起始index=2,结束index=2 // subArray = [99] sum = 99

来看看完整的代码

public int shortestSubarray(int[] A, int K) {
     int endIndex = 0; // 结束index
     int startIndex = 0; // 起始index
     int minLength = Integer.MAX_VALUE; // 最短距离
     int sum = 0; // 总和
     int length = A.length; // 数组总长度
     while (endIndex < length) {
         // sum为0时，起始与结束index相同，如果当前位置为负数，
         // 起始与结束index同时右移
         if (sum == 0 && A[endIndex] <= 0) {
             endIndex++;
             startIndex++;
             continue;
         }
         sum += A[endIndex];
         // sum小于等于0时，之前的元素会成为之后求和的负担，应舍弃                 
         // 起始与结束index同时右移到当前位置的后一位，
         // 因为重置了index并重新开始计算，不要忘了需要将sum清零。
         if (sum <= 0) {
             sum = 0;
             startIndex = endIndex + 1;
             endIndex++;
         } else if (sum >= K) {
             // 满足条件时，记录minLength
             if (endIndex - startIndex + 1 < minLength) {
                 minLength = endIndex - startIndex + 1;
             }
             int tempSum = sum;
             boolean isChanged = false;
             // 右移起始index，取得最优解。
             for (int j = startIndex; j < endIndex; j++) {
                 tempSum -= A[j];
                 if (tempSum >= K && endIndex - j < minLength) {
                     minLength = endIndex - j;
                     startIndex = j + 2;
                     isChanged = true;
                 } else {
                     break;
                 }
             }
             if (!isChanged) {
                 startIndex++;
             }
             endIndex = startIndex;
             sum = 0;
         } else {
             endIndex++;
         }
     }
     return minLength == Integer.MAX_VALUE ? -1 : minLength;
 }

这个解法，虽然有些慢，但还算是好理解。有时间会一起分析下官方给出的答案。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-862-shortest-subarray-with-sum-at-least-k-解题思路分析/