二分查找|滑动窗口|前缀和|LeetCode209: 长度最小的子数组

简介: 二分查找|滑动窗口|前缀和|LeetCode209: 长度最小的子数组

长度最短的子数组

作者推荐

【动态规划】【广度优先】LeetCode2258:逃离火灾

本文涉及的基础知识点

二分查找算法合集

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

滑动窗口

题目

给定一个含有 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

提示:

1 <= target <= 109

1 <= nums.length <= 105

1 <= nums[i] <= 105

枚举开始,二分结尾

时间复杂度:O(nlogn)。

vPreSum是前缀和,已知i,求子数组[i,j)的和大于等于target的最小j。

子数组[i,j)的和等于vPreSum[j]-vPreSum[i] ,大于等于target,则vPreSum[j] >= target + vPreSum[i],我们选择第一个大于等于target + vPreSum[i]的数。

核心代码

class Solution {
public:
  int minSubArrayLen(int target, vector<int>& nums) {
    vector<long long> vPreSum = { 0 };
    for (const auto& n : nums)
    {
      vPreSum.emplace_back(n + vPreSum.back());
    }
    int iRet = INT_MAX;
    for (int i = 0; i < nums.size(); i++)
    {
      int j = std::lower_bound(vPreSum.begin(), vPreSum.end(), target + vPreSum[i]) - vPreSum.begin();
      if (vPreSum.size() == j)
      {
        continue;
      }
      iRet = min(iRet,j-i );
    }
    return (INT_MAX== iRet)? 0 : iRet;
  }
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    assert(v1[i] == v2[i]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  int target;
  vector<int> nums;
  {
    Solution slu;
    target = 7, nums = { 2, 3, 1, 2, 4, 3 };
    auto res = slu.minSubArrayLen(target, nums);
    Assert(2, res);
  }
  {
    Solution slu;
    target = 4, nums = { 1,4,4 };
    auto res = slu.minSubArrayLen(target, nums);
    Assert(1, res);
  }
  {
    Solution slu;
    target = 11, nums = { 1,1,1,1,1,1,1,1 };
    auto res = slu.minSubArrayLen(target, nums);
    Assert(0, res);
  }
  //CConsole::Out(res);
}

二分长度,利用滑动窗口求和

时间复杂度:O(nlogn)。

首先处理特殊情况:不存在合乎要求的子数组。

寻找第一个符合的长度,用左开右闭的二分。

class Solution {
public:
  int minSubArrayLen(int target, vector<int>& nums) {
    if (std::accumulate(nums.begin(), nums.end(), 0LL) < target)
    {
      return 0;
    }
    //左开右闭空间
    int left = 0, right = nums.size();
    while (right - left > 1)
    {
      const int mid = left + (right - left) / 2; 
      auto Is = [&]()
      {       
        long long llSum = 0;
        int i = 0;
        for (; i < mid; i++)
        {
          llSum += nums[i];
        }
        if (llSum >= target)
        {
          return true;
        }
        for (; i < nums.size(); i++)
        {
          llSum += nums[i] - nums[i - mid];
          if (llSum >= target)
          {
            return true;
          }
        }
        return false;
      };
      if (Is())
      {
        right = mid;
      }
      else
      {
        left = mid;
      }
    }
    return right;
  }
};

滑动窗口

两层枚举,第一层从大到小枚举left,第二层枚举right。两层时间复杂度都是O(n),第二层枚举没有从新开始,所以总时间复杂度是O(n)。子数组[left,right)是以下情况之一:

一,[left,right)是第一个小于target的right。

二,right是m_c。对应没有符合要求的以left开始的子数组。

class Solution {
public:
  int minSubArrayLen(int target, vector<int>& nums) {
    m_c = nums.size();
    long long llSum =0;
    int iRet = INT_MAX;
    for (int left = m_c - 1, right = m_c; left >= 0; left--)
    {
      llSum += nums[left];
      while (llSum >= target)
      {
        right--;
        llSum -= nums[right];
      }
      if (m_c != right)
      {
        iRet = min(iRet, right - left + 1);
      }
    }
    return (INT_MAX==iRet)?0:iRet;
  }
  int m_c;
};


。也就是我们常说的专业的人做专业的事。 |

|如果程序是一条龙,那算法就是他的是睛|

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境:

VS2022 C++17

相关文章
|
30天前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
3天前
|
存储
力扣-2904最短且字典序最小的美丽子序列
力扣-2904最短且字典序最小的美丽子序列
6 1
|
24天前
|
人工智能
力扣100114. 元素和最小的山形三元组 II(中等)
力扣100114. 元素和最小的山形三元组 II(中等)
|
30天前
|
索引
leetcode代码记录(最长重复子数组
leetcode代码记录(最长重复子数组
15 0
|
30天前
leetcode代码记录(长度最小的子数组
leetcode代码记录(长度最小的子数组
18 0
|
30天前
【力扣】209. 长度最小的子数组
【力扣】209. 长度最小的子数组
|
30天前
|
算法 测试技术
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
|
18天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
22 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
1天前
|
存储 容器
【LeetCode刷题】只出现一次的数字(Ⅰ、Ⅱ、Ⅲ)
【LeetCode刷题】只出现一次的数字(Ⅰ、Ⅱ、Ⅲ)
|
7天前
|
存储 算法
力扣链表刷题总结(简单)
力扣链表刷题总结(简单)