leetcode209.长度最小子数组（Java）

题目

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。

思路分析

暴力法

  最先想到的自然是暴力法，这也是正常的思路。我认为许多算法问题都是对暴力搜索的优化，这几次参加leetcode周赛感受很深刻。每次做题都是暴力搜索之后超时，优化的步骤每次都有问题。对于该题暴力法的思路如下，两次循环遍历所有可能的连续子数组，然后计算出每个连续子数组的和，该方法的时间复杂度位O(n3)。显然可以事先计算每段(0, i)的和 dp[i]，然后再计算连续子数据的和时，其时间复杂度优化为O(1)，总的时间复杂度变为O(n2)这是很容易就能想到的优化方法。代码如下:

class Solution { public int minSubArrayLen(int s, int[] nums) { int len = nums.length; if (len == 0) return 0; int[] dp = new int[len]; dp[0] = nums[0]; for (int i = 1; i < len; i++) { dp[i] = dp[i-1] + nums[i]; } if (dp[len - 1] < s) return 0; int res = len; for (int i = 0; i < len; i++) { for (int j = i; j < len; j++) { if (dp[j] - dp[i] + nums[i] >= s) { if (j - i + 1 < res) { res = j - i + 1; } } } } return res; } }

利用二分搜索进行优化

在循环的内层，是一个遍历操作，时间复杂度为O(n)。目标是找出一个 j 使得： $$dp[j]-dp[i]+nums[i]>=s$$ 同样可以转换为找到一个 j 使得： $$dp[j]>=s+dp[i]-nums[i]$$ 即找到一个大于等于某值 target 的 dp[j]，显然这可以利用二分搜索进行查找。 这是一个典型的二分搜索程序：

private int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else right = mid - 1; } return -1; }

要对二分搜索有一定的理解：

该二分搜索结束时，left 和 right 有两种情况。找到了target，此时 left=right ；未找到target，此时left < right。未找到target时，nums[left] 为第一个大于target的值，nums[right] 为第一个小于target的值。当target不在nums的(min, max) 范围内时，没有大于或者小于target的nums[i]，此时left = nums.length 或者 right = -1。同样，有一种更加直观的理解，right 在target 值所在位置的左边，left 在target值所在位置的右边。

基于以上理解，left就是大于等于target值的索引。此时，left 等于 nums.length 时，说明该索引不合法；left < nums.length 时，该索引合法，能找到一个大于等于某值target的 dp[j]。其余步骤较为简单，代码如下：

class Solution { public int minSubArrayLen(int s, int[] nums) { int len = nums.length; if (len == 0) return 0; int[] dp = new int[len]; dp[0] = nums[0]; for (int i = 1; i < len; i++) { dp[i] = dp[i-1] + nums[i]; } if (dp[len - 1] < s) return 0; // 如果不存在 int res = len; for (int i = 0; i < len; i++) { // 从 i 到 j : dp[j] - dp[i] + nums[i] >= s int target = s + dp[i] - nums[i]; // 找到大于等于 target的那个j int j = binarySearch(dp, target); if (j < len) { if (j - i + 1 < res) res = j - i + 1; } } return res; } private int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else right = mid - 1; } return left; } }