【leetcode】209. 长度最小的子数组

题目内容

209. 长度最小的子数组

思路分析

参考资料

方法一：前缀和+二分查找

由于题目所给的数组元素都是正整数，且要找到满足≥target的子序列。

因此，设题目所给数组的大小为n，可以创建一个大小为n+1的数组sums，其第i个元素为前i个数字的和，则问题转换为：

对于指定的下标i，求满足sums[j]-sums[i]≥target的最小j。则子序列长度为j-i（可在纸上举例，写出nums数组、sums数组、sums数组的下标即可看出来）。再比较出各个i中较小的那个子序列长度即可。

其中，数组sum的大小为i+1是非常有必要的，因为要包含前0个元素和的这种情况，即连续子序列是前若干个数的情况。

而求满足sums[j]-sums[i]≥target的最小j即求满足sums[j]≥target+sum[i]的最小j，这个问题可以使用二分查找来解决，或是直接使用C++提供的lower_bound函数，该函数的作用是找到指定范围内大于等于指定数的第一个数的位置。

此外应注意到找不到≥target的子序列这种情况。

方法二：滑动窗口（双指针）

参考资料

暴力法（本题解没写出来）是对于每个下标i，线性查找满足条件的值，因此时间复杂度为O(n^2)。

而前缀和+二分查找是对于每个下标i，二分查找满足条件的值，因此时间复杂度为O(nlogn)。

在这两种算法中，对于每个下标i，都需要重新遍历一遍数组/剩余数组，因此时间复杂度较高。

这里可以使用滑动窗口（双指针）来优化时间复杂度。

具体做法是使用两个指针left和right，right先向右移动，直至[left, right]范围内的数字和满足≥target，然后开始向右移动left指针，缩小窗口，并更新满足条件的序列长度。这样left和right加起来最多移动2n次，算法的时间复杂度变为O(n)。

代码

#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

// 前缀和+二分查找
// 时间复杂度O(nlogn)
// 空间复杂度O(n)
class Solution1 {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
       int n = nums.size();
       vector<int> prefix_sums; // prefix_sums[i]前i个元素的和
       prefix_sums.push_back(0);

       for (int i = 0; i < n; ++i) {
          prefix_sums.push_back(prefix_sums[i] + nums[i]);
       }

       int min_subarray_len{INT_MAX};
       for (int i = 0; i <= n; ++i) {
          int bound_position = lower_bound(prefix_sums.begin(), 
             prefix_sums.end(), prefix_sums[i] + target) - 
             prefix_sums.begin();
          if (bound_position == n + 1) continue; // 没有满足条件的子序列
          min_subarray_len = min(min_subarray_len, bound_position - i);
       }
       return  min_subarray_len == INT_MAX ? 0 : min_subarray_len;
    }
};

// 滑动窗口（双指针）
// 时间复杂度O(n)，两个指针各最多总共移动n次
// 空间复杂度O(1)
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
       int n = nums.size();
       int left{ 0 }, right{ 0 }, sum{ 0 }, min_subarray_len{ INT_MAX };

       for (right = 0; right < n; ++right) {
          sum += nums[right];
          while (sum >= target) {
             min_subarray_len = min(min_subarray_len, right - left + 1);
             sum -= nums[left];
             ++left;
          }
       }

       return min_subarray_len == INT_MAX ? 0 : min_subarray_len;
    }
};

int main() {
   Solution s;
   int result = 0;
   int target = 7;
   vector<int> input{ 2,3,1,2,4,3 };
   result = s.minSubArrayLen(target, input);
   int a = 0;
}

收获

开始动手编码之前应该先想清楚思路，不然越写越乱
可以通过编码前想各种测试用例的方式提高所写代码的鲁棒性
二分查找（lower_bound）用的还是挺多的