长度最小的子数组

leercode链接

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

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

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

思路

本题的暴力解法思路是两个for循环，时间复杂度是O(\(n^2\))。对于数组的两个for循环问题，我们通常想到的是否能一个for循环解决问题。前一篇博客提到使用快慢指针，其本质是双指针。那么这道题思考一下是否也能用双指针来解决。

本题需要我们找出最小的连续序列，那么可以想到，如果使用双指针，right指针进行遍历，left指针进行尾部检测，是否就可以解决问题了呢？left尾部检测的关键点有两点，一是需要计算当前区间内所有值的总和是否大于等于target，二是当前区间的长度是否为最小。针对这两点，代码可以写为：

while(sum >= target) //sum表示当前滑动窗口内数字的总和
{
  len = right - left + 1;//计算窗口长度
  result = result < len ? result : len;//判断当前满足条件的窗口是否为最小
  sum -= num[left++];//窗口左边收缩，
}

有了关键步骤之后，完整代码可以写为：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int res = INT32_MAX;
        int sum = 0; //窗口内的数组和
        int left = 0;//窗口开始
        int len = 0; //窗口大小
        for(int right=0; right<n; ++right)
        {
            sum += nums[right];
            while(sum>=target)
            {
                len = right - left + 1;
                res = res < len ? res : len;
                sum -= nums[left++];
            }
        }
        return res == INT32_MAX ? 0 : res;
    }
};

相关题目

水果成篮

题目

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

  • 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
  • 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

思路

这道题与基础的滑动窗口不同的点在于，需要记录已经存在的水果。在这里我们很容易想到使用哈希表进行存储。key为水果种类，value为出现次数。当key超过2时，则说明有新水果出现，此时需要让left进行收缩。那如何判断收缩到合理位置呢？即，删除当前map中的水果，并且left右移一次。以此类推，直到某一种水果的value变为0则说明该水果已经被删除。整体代码可以写为

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> count;
        int left = 0;
        int n = fruits.size();
        int max = 0;
        for(int right = 0; right < n; ++right)
        {
            count[fruits[right]]++;

            // 窗口内水果超过两种
            while(count.size() > 2)
            {
                count[fruits[left]]--;
                if(count[fruits[left]] == 0){
                    count.erase(fruits[left]); // 删除当前水果
                }
                left++;
            }
            // 更新最大水果数
            //max = std::max(max, right - left + 1);
            max = max > (right - left + 1) ? max : (right - left + 1);
        }
        return max;
    }
};