【优选算法】（第五篇）

目录

⻓度最⼩的⼦数组（medium）

题目解析

讲解算法原理

编写代码

⽆重复字符的最⻓⼦串（medium）

题目解析

讲解算法原理

编写代码

⻓度最⼩的⼦数组（medium）

题目解析

1.题目链接：. - 力扣（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
⽰例3：
输⼊： target = 11, nums = [1,1,1,1,1,1,1,1]
输出： 0

讲解算法原理

解法⼀（暴⼒求解）（会超时）：
算法思路：
「从前往后」枚举数组中的任意⼀个元素，把它当成起始位置。然后从这个「起始位置」开始，然后寻找⼀段最短的区间，使得这段区间的和「⼤于等于」⽬标值。
将所有元素作为起始位置所得的结果中，找到「最⼩值」即可。

算法代码：

class Solution {
public:
 int minSubArrayLen(int target, vector<int>& nums) {
 // 记录结果
 int ret = INT_MAX;
 int n = nums.size();
 // 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end] // 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩ // 枚举开始位置
 for (int start = 0; start < n; start++)
 {
 int sum = 0; // 记录从这个位置开始的连续数组的和 // 寻找结束位置
 for (int end = start; end < n; end++)
 {
 sum += nums[end]; // 将当前位置加上
 
 if (sum >= target) // 当这段区间内的和满⾜条件时 {
 // 更新结果，start 开头的最短区间已经找到 ret = min(ret, end - start + 1);
 break;
 }
 }
 }
 // 返回最后结果
 return ret == INT_MAX ? 0 : ret;
 }
};

解法⼆（滑动窗⼝）：
算法思路：
由于此问题分析的对象是「⼀段连续的区间」，因此可以考虑「滑动窗⼝」的思想来解决这道题。让滑动窗⼝满⾜：从 i 位置开始，窗⼝内所有元素的和⼩于 target （那么当窗⼝内元素之和
第⼀次⼤于等于⽬标值的时候，就是 i 位置开始，满⾜条件的最⼩⻓度）。做法：将右端元素划⼊窗⼝中，统计出此时窗⼝内元素的和：
▪ 如果窗⼝内元素之和⼤于等于 target ：更新结果，并且将左端元素划出去的同时继续判
断是否满⾜条件并更新结果（因为左端元素可能很⼩，划出去之后依旧满⾜条件）▪ 如果窗⼝内元素之和不满⾜条件： right++ ，另下⼀个元素进⼊窗⼝。
相信科学（这也是很多题解以及帖⼦没告诉你的事情：只给你说怎么做，没给你解释为什么这么做）：
为何滑动窗⼝可以解决问题，并且时间复杂度更低？
▪ 这个窗⼝寻找的是：以当前窗⼝最左侧元素（记为 left1 ）为基准，符合条件的情况。也
就是在这道题中，从 left1 开始，满⾜区间和 sum >= target 时的最右侧（记为
right1 ）能到哪⾥。
▪ 我们既然已经找到从 left1 开始的最优的区间，那么就可以⼤胆舍去 left1 。但是如
果继续像⽅法⼀⼀样，重新开始统计第⼆个元素（ left2 ）往后的和，势必会有⼤量重复的计算（因为我们在求第⼀段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候⽤上的）。
▪ 此时， rigth1 的作⽤就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从
right1 这个元素开始，往后找满⾜ left2 元素的区间（此时 right1 也有可能是满
⾜的，因为 left1 可能很⼩。 sum 剔除掉 left1 之后，依旧满⾜⼤于等于
target ）。这样我们就能省掉⼤量重复的计算。
▪ 这样我们不仅能解决问题，⽽且效率也会⼤⼤提升。
时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者最多都往后移动 n 次。因此时间复杂度是 O(N) 。

如图所示：

在left每次加加的时候，减去前一个left值，这样right就不需要再返回来进行一个运算，大大节省了空间复杂度 

编写代码

c++算法代码：

class Solution
{
public:
 int minSubArrayLen(int target, vector<int>& nums) 
 {
 int n = nums.size(), sum = 0, len = INT_MAX;
 for(int left = 0, right = 0; right < n; right++)
 {
 sum += nums[right]; // 进窗⼝
 while(sum >= target) // 判断
 {
 len = min(len, right - left + 1); // 更新结果
 sum -= nums[left++]; // 出窗⼝
 }
 }
 return len == INT_MAX ? 0 : len;
 }
};

java算法代码：

class Solution
{
 public int minSubArrayLen(int target, int[] nums) 
 {
 int n = nums.length, sum = 0, len = Integer.MAX_VALUE;
 for(int left = 0, right = 0; right < n; right++)
 {
 sum += nums[right]; // 进窗⼝
 while(sum >= target) // 判断
 {
 len = Math.min(len, right - left + 1); // 更新结果 sum -= nums[left++]; // 出窗⼝
 }
 }
 return len == Integer.MAX_VALUE ? 0 : len;
 }
}

⽆重复字符的最⻓⼦串（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目讲解

给定⼀个字符串s，请你找出其中不含有重复字符的最⻓⼦串的⻓度。
⽰例1:
输⼊: s = "abcabcbb"
输出: 3
解释:因为⽆重复字符的最⻓⼦串是 "abc" ，所以其⻓度为 3 。⽰例2:
输⼊: s = "bbbbb"
输出: 1
解释:因为⽆重复字符的最⻓⼦串是 "b" ，所以其⻓度为 1 。⽰例3:
输⼊: s = "pwwkew"
输出: 3
解释:因为⽆重复字符的最⻓⼦串是 "wke" ，所以其⻓度为 3 。请注意，你的答案必须是⼦串的⻓度， "pwke" 是⼀个⼦序列，不是⼦串。

提⽰：
• 0 <= s.length <= 5 * 10^4
• s 由英⽂字⺟、数字、符号和空格组成1.

讲解算法原理

解法⼀（暴⼒求解）（不会超时，可以通过）：
算法思路：
枚举「从每⼀个位置」开始往后，⽆重复字符的⼦串可以到达什么位置。找出其中⻓度最⼤的即可。
在往后寻找⽆重复⼦串能到达的位置时，可以利⽤「哈希表」统计出字符出现的频次，来判断什么时候⼦串出现了重复元素。

算法代码：

class Solution {
public:
 int lengthOfLongestSubstring(string s) {
 int ret = 0; // 记录结果
 int n = s.length();
 // 1. 枚举从不同位置开始的最⻓重复⼦串
 // 枚举起始位置
 for (int i = 0; i < n; i++)
 {
 // 创建⼀个哈希表，统计频次
 int hash[128] = { 0 };
 
 // 寻找结束为⽌
 for (int j = i; j < n; j++)
 {
 hash[s[j]]++; // 统计字符出现的频次 if (hash[s[j]] > 1) // 如果出现重复的
 break;
 
 // 如果没有重复，就更新 ret
 ret = max(ret, j - i + 1);
 }
 }
 // 2. 返回结果
 return ret;
 }
};

解法⼆（滑动窗⼝）：
算法思路：
研究的对象依旧是⼀段连续的区间，因此继续使⽤「滑动窗⼝」思想来优化。让滑动窗⼝满⾜：窗⼝内所有元素都是不重复的。
做法：右端元素 ch 进⼊窗⼝的时候，哈希表统计这个字符的频次：
▪ 如果这个字符出现的频次超过 1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝，
直到 ch 这个元素的频次变为 1 ，然后再更新结果。▪ 如果没有超过 1 ，说明当前窗⼝没有重复元素，可以直接更新结果 

如图所示：
在出现重复字符之后，left一直移动到重复字符之后，这样的话left可以进行一次小优化，并且整个数组只需要遍历一次，时间复杂度非常可观！ 

编写代码

c++算法代码：

class Solution
{
public:
 int lengthOfLongestSubstring(string s) 
 {
 int hash[128] = { 0 }; // 使⽤数组来模拟哈希表 int left = 0, right = 0, n = s.size();
 int ret = 0;
 while(right < n)
 {
 hash[s[right]]++; // 进⼊窗⼝
 while(hash[s[right]] > 1) // 判断
 hash[s[left++]]--; // 出窗⼝
 ret = max(ret, right - left + 1); // 更新结果 right++; // 让下⼀个元素进⼊窗⼝
 }
 return ret;
 }
};

java算法代码：

class Solution
{
 public int lengthOfLongestSubstring(String ss) 
 {
 char[] s = ss.toCharArray();
 int[] hash = new int[128]; // ⽤数组模拟哈希表 int left = 0, right = 0, n = ss.length();
 int ret = 0;
 while(right < n)
 {
 hash[s[right]]++; // 进⼊窗⼝
 while(hash[s[right]] > 1) // 判断
 hash[s[left++]]--; // 出窗⼝
 ret = Math.max(ret, right - left + 1); // 更新结果 right++; // 让下⼀个字符进⼊窗⼝
 }
 return ret;
 }
}