209. 长度最小的子数组

题目描述 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例:  输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 https://leetcode-cn.com/problems/minimum-size-subarray-sum/ 解法1 – 朴素算法O(n^2) 解法1使用朴素算法,我们使用指针i, j(0<=i<=j<|nums|)来描述子数组,然后计算i到j区间元素到和,如果大于等于s则取j – i + 1作为可能到解ans;如果小于s则j右移。为了实现O(1)时间复杂度的区间求和,我们可以使用prefix sum算法预先计算前缀和。当指针i和j扫描完所有的连续区间,我们取最小的解就是答案。如果找不到子数组当和大于等与s,就返回0。 需要注意一点,当找到一对i, j我们就可以退出内层循环。因为继续找下去的子序列长度已定大于(i-j+1),否则会TLE。算法的时间复杂度为O(n^2),空间复杂度为O(n) (存放前缀和)。全部代码如下: 解法2 – 优化的朴素算法O(nlogn) 我们沿用解法1的思路,但是对寻找连续区间上进行优化。我们让i = [0, |nums|),使用二分搜索寻找j,其中i <= j < |nums|。因为我们有前缀和数组prefix,我们可以在O(logn)的时间内找到一个下界(lower bound),使得prefix[j] – prefix[i] >= s。那么,j – i +1就是其中一个解,当i遍历完整个数组时,就取最小的那个解作为答案。…

Read more

239. 滑动窗口最大值

题目描述 给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。 返回滑动窗口最大值。 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 ————— —– [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5…

Read more

3. 无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。 示例 3: 输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。   请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ 解法1 思路:使用双层循环,外层循环取字符串s的每个位置,内层循环取外层循环的值至字符串末尾。在内层循环中创建一个范围为0-255的boolean数组用来判断字符是否重复出现,这比HashMap更加轻量。最后,使用一个名为maxLen的变量存放最终结果,我们在内层循环更新这个变量。 解法2 解法一采用了双重循环,时间复杂度是O(n^2)的,我们可以使用滑动窗口方法,维护一个[i, j),0<=i<j<=|s|的窗口,确保窗口内的字串不含重复字符。窗口的前沿是j,后沿是i。前沿滑动,直到加入到窗口内的字符出现重复。此时,我们滑动窗口后沿,直到窗口内不含重复字符。我们在窗口前沿滑动时,计算maxLen = max(maxLen, i – j). 因为是左闭右开区间,直接用i-j就是窗口的大小。 参考:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/

Read more