☆打卡算法☆LeetCode 209. 长度最小的子数组 算法解析
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个整数数组和正整数target,找出数组中满足≥target
的长度最小的子数组,返回其长度。”
题目链接:
来源:力扣(LeetCode)
链接: 209. 长度最小的子数组 - 力扣(LeetCode)
2、题目描述
给定一个含有 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
二、解题
1、思路分析
这道题要找出该数组中满足其和 ≥ target 的长度最小的连续子数组。
直观的方法是枚举数组中每个下标i作为子数组的开始下标,找到满足条件的下标j,然后更新子数组的最小长度也就是j-i+1,但是这种方法实现可能会超出时间限制。
上面说的方法时间复杂度为O(n2),因为找到长度最小的子数组需要O(n)的时间,要全部找一遍需要O(n2)的时间复杂度,那么能不能将时间优化一下呢。
常见的优化方法,可以使用二分查找,就可以将时间复杂度优化到O(log n),使用二分查找,需要创建一个数组用于存储数组的前缀和,前缀和就是从位置1到位置i这个区间内的所有的数字之和,对于每个开始下标i,通过二分查找得到大于或等于i的最小下标,更新子数组的最小长度。
2、代码实现
代码参考:
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int[] sums = new int[n + 1];
// 为了方便计算,令 size = n + 1
// sums[0] = 0 意味着前 0 个元素的前缀和为 0
// sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
// 以此类推
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= n; i++) {
int target = s + sums[i - 1];
int bound = Arrays.binarySearch(sums, target);
if (bound < 0) {
bound = -bound - 1;
}
if (bound <= n) {
ans = Math.min(ans, bound - (i - 1));
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
3、时间复杂度
时间复杂度:O(n log n)
其中n是数组的长度,需要遍历每个下标作为子数组的开始下标,通过二分查找得到长度最小的子数组,二分查找的时间复杂度是O(log n),总时间复杂度为O(n log n)。
空间复杂度:O(n)
其中n是数组的长度。
三、总结
因为这道题保证了数组中的每个元素都是正值。
那么前缀和一定是递增的,可以保证二分查找是不会出现问题的。
如果数组中不是每个元素都为正的话,就不能使用二分来查找位置了。
相关文章
- ☆打卡算法☆LeetCode 207. 课程表 算法解析
- ☆打卡算法☆LeetCode 208. 实现 Trie (前缀树) 算法解析
- ☆打卡算法☆LeetCode 214. 最短回文串 算法解析
- ☆打卡算法☆LeetCode 215. 数组中的第K个最大元素 算法解析
- LeetCode笔记:Weekly Contest 303
- 日拱一卒,LeetCode周赛287,训练你的逆向思维
- LeetCode刷题系列(3)
- ☆打卡算法☆LeetCode 188. 轮转数组 算法解析
- leetcode刷题(132)——完全背包问题思路理解
- LeetCode 刷题笔记——day 4
- LeetCode 7. 整数反转
- 前端工程师leetcode算法面试必备-简单的二叉树
- 【数据结构与算法】:交换排序之快速排序(手绘图解+LeetCode原题)
- Remove Duplicates from Sorted Array — LeetCode
- 前端工程师leetcode算法之二叉树的构造和遍历
- js刷leetcode动态规划(图文视频讲解)
- 初学LeetCode算法题电话号码的字母组合(虽然不难但是做出来还是很爽的)
- 前端工程师leetcode算法面试必备-二叉树的构造和遍历1
- 前端工程师leetcode算法面试必备-简单的二叉树
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇5
- 【算法】动态规划 ③ ( LeetCode 62.不同路径 | 问题分析 | 自顶向下的动态规划 | 自底向上的动态规划 )
- leetcode 71. 简化路径