LeetCode刷题——长度最小的子数组#209#Medium_29长度最小的数组

长度最小的子数组的思路探讨与源码
    长度最小的子数组的题目如下图，该题属于搜索类和数组类型的题目，主要考察对于搜索方法的使用和数组结构的理解。本文的题目作者想到2种方法，分别是二分查找方法和滑动窗口方法，其中二分查找方法使用Java进行编写，而滑动窗口方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

    本人认为该题目可以使用二分查找方法的思路进行解决，首先计算数组的长度并进行初始化，得到一个数组，再对原有的数组进行遍历，得到一个累计求和值的数组，即新数组的第一个元素是0，后面的每个元素都是输入数组的前N个元素的求和值。然后开始遍历数组，计算目标值和新数组元素的和，然后用二分搜索找到对应的下标，对下标进行非运算后就是分界点的下标位置，并判断这个分界点是否比原有数组的长度要小，如果是就更新最小的数组长度值，最终直到遍历结束。对最小的子数组长度值进行判断，如果和初始值相等就返回0，否则就返回最小的子数组长度值。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int numLen = nums.length;
        int minNum = Integer.MAX_VALUE;
        int[] sumArr = new int[numLen + 1];
        for (int jr = 1; jr <= numLen; jr++) {
            sumArr[jr] = sumArr[jr - 1] + nums[jr - 1];
        }
        for (int kr = 0; kr <= numLen; kr++) {
            int subSum = target + sumArr[kr];
            int ind = Arrays.binarySearch(sumArr,subSum);
            if (ind < 0)
                ind = ~ind;
            if (ind <= numLen) {
                minNum = Math.min(minNum, ind - kr);
            }
        }
        if(minNum == Integer.MAX_VALUE){
            return 0;
        }else{
            return minNum;
        }
    }
}
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

    显然，我们看到二分查找的方法效果比较差，同时还可以使用滑动窗口方法解决。首先进行参数的初始化，将下标与历史求和值都设置为0，并计算数组的长度。然后开始遍历数组，每次都先更新历史求和值为上一次求和值和当前元素的和，并且开始子循环，如果目标值比历史求和值要小就进行子循环，判断并更新子数组长度的最小值，然后对历史求和值减去下标为ind的数组值并更新，再将下标移动一位，直到最终循环结束。最后判断子数组长度的值是否和初始值相等，如果相等就返回0，否则就返回最终的子数组长度值。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        ind=0
        sumNum=0
        resFinal=float("inf")
        numLen=len(nums)
        for jr in range(numLen):
            sumNum=sumNum+nums[jr]
            while(target<=sumNum):
                resFinal=min(jr-ind+1,resFinal)
                sumNum=sumNum-nums[ind]
                ind=ind+1
        if resFinal==float("inf"):
            return 0
        else:
            return resFinal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

    从结果来说Java版本二分查找方法的效率比较差，而Python版本的滑动窗口方法的速度也比较一般，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。