LeetCode Hot 100 刷题 [21-30]
2023-07-15 17:48:48
LeetCode Hot 100 [11-20]
刷完了《剑指Offer》,下一阶段,开始 LeetCode Hot 100。 之前一直都用思维导图记录,今天发现思维导图可以导出成markdown,简单编辑一下就可以成为文章。相比Xmind,博客文章打开和查看更加方便,所以之后每次Xmind记录之后,会再在这里同时同步一下
前言
HOT100,之前的文章传送门
LeetCode Hot 100 刷题 [1-10]
LeetCode Hot 100 刷题 [11-20]
21.接雨水问题
题目
- 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
- 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
- 输出: 6
- 题目地址
- 这是一道Hard题
解题思路
思路1:暴力算法
- 按列,统计每个列上可以存的雨水的量
- 如何计算某个列上存水的量
- 遍历找出该列左边的最大高度,maxleft
- 遍历找出该列右边的最大高度,maxRight
- 水的高度取决于maxLeft和maxRight中的较小者
- 这个列上水的深度为水的高度 - 该列的高度
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public int trap(int[] height) {
int res = 0;
for(int i =0; i < height.length; i++){
// find max left
int leftMax = 0;
for(int j = 0; j < i; j++){
leftMax = Math.max(leftMax, height[j]);
}
// find max right
int rightMax = 0;
for(int j = i+1; j<height.length; j++){
rightMax = Math.max(rightMax, height[j]);
}
int validHeight = Math.min(leftMax,rightMax);
res += Math.max(0, validHeight-height[i]);
}
return res;
} - 算法复杂度
- 时间复杂度O(N^2)
思路2:动态规划
- 对思路1进行优化,思路1中查找左右最大值的过程可以通过DP优化
- 定义maxLeftDP[ i ] 为 i 左边的最大高度,同理,maxRightDp[ i ]为 i 右边的最大高度
- maxLeftDP[ i ] = Max{ maxLeftDP[ i-1 ] , height[ i-1 ] }
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public int trap(int[] height) {
int res = 0;
int [] maxLeftDP = new int [height.length];
int [] maxRightDP = new int [height.length];
int size = height.length;
for(int i = 1; i < size-1; i++){
maxLeftDP[i] = Math.max(maxLeftDP[i-1], height[i-1]);
maxRightDP[size-1- i] = Math.max(maxRightDP[ size-i], height[size-i]);
}
for(int i = 1; i < height.length-1; i++){
int validHeight = Math.min(maxLeftDP[i],maxRightDP[i]);
res += Math.max(0, validHeight-height[i]);
}
return res;
} - 复杂度分析
- 时间复杂度O(N)
- 空间复杂度O(N)
思路3:双指针解法
- 对思路2中的空间复杂度还可以进一步优化
- DP递推方程中,maxLeft和maxRight其实只用到左右边的一个,其实可以不用数组来存储
- maxLeftDP是直接可以用变量来替代的,但是maxRightDP的求解是从右向左的,不方便直接用变量来替代
- 思路与过程
- left、right双指针从两端进行更新
- maxLeft、maxRight记录left和right位置对应的左右最大值
- maxLeft和maxRight中,起作用的是他们中的较小值,所以每次left和right指针更新较小值的一端
- 如何选择更新哪一段
- maxLeft < maxRight
- 可以保证maxLeft为left左边最大值,且它是起作用的
- left指针前进,同时更新maxleft
maxLeft > maxRight - 同理,可以保障maxRight为right右边最大值,且它比maxLeft要小,所以即便加上右边还没检查的部分,最终的maxLeft还是比maxRight大,即起作用的还是maxRight
- 所以,right指针前进,同时更新maxRight
- 让我想起了类似的用双指针求最大面积的题目
- 每次搜索高度较小的一边
- maxLeft < maxRight
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public int trap(int[] height) {
int res = 0;
int left = 0, right = height.length - 1;
int maxLeft = 0, maxRight = 0;
while( left <= right){
// maxLeft 起作用
if( height[left] < maxRight && maxLeft < maxRight ){
if( height[left] > maxLeft ){
maxLeft = height[left];
}else{
res += maxLeft - height[left];
}
left++;
} else { // maxRight 起作用
if( height[right] > maxRight ){
maxRight = height[right];
}else{
res += maxRight - height[right];
}
right--;
}
}
return res;
} - 复杂度分析
- 时间复杂度O(N)
- 空间复杂度O(1)
22.旋转图像
题目
- 给定一个 n × n 的二维矩阵表示一个图像。
- 将图像顺时针旋转 90 度。
- 你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
- 给定 matrix =
1
2
3
4
5[
[1,2,3],
[4,5,6],
[7,8,9]
] - 原地旋转输入矩阵,使其变为:
1
2
3
4
5[
[7,4,1],
[8,5,2],
[9,6,3]
] - 题目地址
解题思路
思路1:转置+行交换
- 思路与过程
- 将行按照对称的方式进行交换
- a[i][j] 与 a[ len-i-1 ][j]交换
- 将处理后的矩阵按对角进行转置
- a[i][j] 与 a[j][i]交换
- 将行按照对称的方式进行交换
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30public void rotate(int[][] matrix) {
// 水平交换
int left = 0, right = matrix.length-1;
while( left < right){
for(int i = 0; i < matrix[0].length;i++){
rowSwap(matrix, left, right, i);
}
left++;
right--;
}
// 对角线对称
for(int i = 0; i<matrix.length; i++){
for(int j = 0; j< i; j++){
angleSwap(matrix,i,j);
}
}
}
private void rowSwap(int [][] matrix, int left, int right , int i){
int temp = matrix[left][i];
matrix[left][i] = matrix[right][i];
matrix[right][i] = temp;
}
private void angleSwap(int [][] matrix, int i, int j){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
} - 复杂度评估
- 时间复杂度O(N^2)
23.字母异位词分组
题目
- 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
- 输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
- 输出:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
```
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
- [题目地址](https://leetcode-cn.com/problems/group-anagrams/)
### 解题思路
#### 思路1:排序 + HashMap
- 对每一个字符串的字符按字典序进行排序
- 将排序后的结果作为HashMap的key,value为列表
- 最终将HashMap的values输出为列表
- values(),返回的是数组,不是List,需要将数组转化成list
- Java8 Stream API:`hashMap.values().stream().collect(Collectors.toList())`
- Java8之前:`new ArrayList(hashMap.values())`
- 代码实现
```java
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> hashMap = new HashMap();
for(String str : strs){
char [] values = str.toCharArray();
Arrays.sort(values);
String key = new String(values);
if(hashMap.containsKey(key)){
hashMap.get(key).add(str);
}else{
List<String> list = new ArrayList();
list.add(str);
hashMap.put(key,list);
}
}
return hashMap.values().stream().collect(Collectors.toList());
} - 复杂度分析
- 时间复杂度O(Nklogk)
- 空间复杂度O(NK)
思路2:字符计数 + HashMap
- 与思路1基本类似,只是key的生成方式不一样
- 思路1需要排序,O(klogk),还是比较高的
- 可以统计每个字符串中26个字母出现的次数,作为模式,模式作为hashmap的key
- 计数模式:
int [ ] count = new int [26]
- 最后的模式串:
1#0#6#...
- 计数模式:
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> hashMap = new HashMap();
int [] count = new int [26];
for(String str : strs){
char [] values = str.toCharArray();
Arrays.fill(count, 0);
for(char ch : values){
count[ch-'a']++;
}
StringBuilder builder = new StringBuilder();
for(int num:count){
builder.append(num);
builder.append(',');
}
String key = builder.toString();
if(hashMap.containsKey(key)){
hashMap.get(key).add(str);
}else{
List<String> list = new ArrayList();
list.add(str);
hashMap.put(key,list);
}
}
return hashMap.values().stream().collect(Collectors.toList());
} - 复杂度分析
- 时间复杂度O(NK)
- 空间复杂度O(NK)
24.跳跃游戏
题目
- 给定一个非负整数数组,你最初位于数组的第一个位置。
- 数组中的每个元素代表你在该位置可以跳跃的最大长度。
- 判断你是否能够到达最后一个位置。
- 输入: [2,3,1,1,4]
- 输出: true
- 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
- 题目地址
解题思路
思路1:排除法
- 研究什么时候跳不到终点
- 序列中有 0 的时候,才会可能跳不到终点
- 当 0 前边所有的数都无法跳过 0 ,则必定跳不过去
- 即该位置的值,小于等于该位置距离0的格数
- 最后一个为0不影响
- 思路过程
- 遍历数组,检索所有的0
- 最后一个位置是否为0不影响,所以不用判断
- 对每一个0, 向前遍历,是否存在能跳跃过它的数
- 所有的都满足,则可以到达最后一个位置
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13public boolean canJump(int[] nums) {
for(int i=0; i < nums.length-1; i++){
// 最后一个是0还是非0对结果不影响
if(nums[i] == 0){
int j,dis=1;
for(j = i-1; j >= 0; j--,dis++){
if(nums[j] > dis) break;
}
if(j < 0) return false;
}
}
return true;
} - 复杂度分析
- 时间复杂度O(N^2)
- 空间复杂度O(1)
思路2:贪心算法
- 是本题的最优解法,也应该是主要的考察点
- 比较不容易想到贪心规则
- 某一位置可达,则该位置之前的位置均是可达的
- 所以,只要保障能到达的位置超过数组最后一个位置就可以了
- 因此,每次都尽可能的向远处跳
- 思路过程
- mostFarIndex 标识目前能到达的最远位置
- 当前位置在最远位置或之前,则说明最远位置可能还可以更大,更新最远位置
- 若当前位置在最远位置之后了,则最远位置再也没法更新了,也就最终无法超越最后一个位置了
代码实现
1
2
3
4
5
6
7
8
9
10
11
12public boolean canJump(int[] nums) {
int mostFarIndex = 0;
for(int i=0; i < nums.length-1; i++){ // 最后一个不影响
if( i <= mostFarIndex ){
mostFarIndex = Math.max(mostFarIndex, i + nums[i]);
if(mostFarIndex >= nums.length-1) return true;
} else {
return false;
}
}
return mostFarIndex >= nums.length-1;
}复杂度分析
- 时间复杂度O(N)
- 空间复杂度O(1)
25.合并区间
题目
- 出一个区间的集合,请合并所有重叠的区间。
- 示例
- 输入: [[1,3],[2,6],[8,10],[15,18]]
- 输出: [[1,6],[8,10],[15,18]]
- 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
- 题目链接
解题思路
- 先将区间按照左边界的大小排序
- lambda实现
1
2
3Arrays.sort(intervals, (int [] a, int [] b)->{
return a[0] - b[0];
});
- lambda实现
- 然后遍历区间数组,相邻的区间能合并则合并
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public int[][] merge(int[][] intervals) {
if(intervals.length == 0) return new int[0][0];
ArrayList<int []> res = new ArrayList();
// 按第一个排序
Arrays.sort(intervals, (int [] a, int [] b)->{
return a[0] - b[0];
});
int start = intervals[0][0], end = intervals[0][1];
for(int i = 0; i<intervals.length; i++){
if(intervals[i][0] <= end){
end = Math.max(end, intervals[i][1]);
}else{
res.add(new int[]{start, end});
start = intervals[i][0];
end = intervals[i][1];
}
}
res.add(new int[]{start, end});
return res.toArray(new int[res.size()][2]);
} - 复杂度分析
- O(NlogN)
26.不同路径
题目
- 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
- 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
- 问总共有多少条不同的路径?
- 题目链接
解题思路
- 典型的深度优先遍历,动态规划解题
思路1:DFS+回溯
- 从左上角出发,分别尝试向下和向右,然后回溯
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
private int count = 0;
public int uniquePaths(int m, int n) {
dfs(0,0,m,n);
return count;
}
private void dfs(int i, int j, int m, int n){
if(i >= m || j >= n) return;
if( i == m-1 && j == n-1){
count++;
return ;
}
// 向右尝试
if(j < n-1){
dfs(i,j+1,m,n);
}
// 向左尝试
if(i < m -1){
dfs(i+1, j, m,n);
}
}
} - 复杂度分析
- 时间复杂度O((M+N)^2)
- 空间复杂度O((M+N)^2)
思路2:动态规划
- dp[ i ][ j ]:到达坐标(i,j)位置有多少个路径
- = dp[ i-1 ]dp[ j ] + dp[ i ][ j-1 ]
- 思路过程
- 创建二维dp数组,并进行初始化
- dp数组的第一行和第一类初始化为1,因为可以确定只有1个路径
- 对dp数组进行填表操作
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13public int uniquePaths(int m, int n) {
int [][] dp = new int [m][n];
Arrays.fill(dp[0], 1);
for(int i = 0; i < m; i++){
dp[i][0] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
} - 复杂度分析
- 时间复杂度O(M*N)
- 空间复杂度O(M*N)
思路3:动态规划空间优化
- 思路2中的dp二维数组,可以继续优化成一维数组
- 因为递归关系中,只使用到了坐标左边和左边上边的位置
- 代码实现
1
2
3
4
5
6
7
8
9
10public int uniquePaths(int m, int n) {
int [] dp = new int [n];
Arrays.fill(dp, 1);
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[j] = dp[j-1] + dp[j];
}
}
return dp[n-1];
}
27. 最小路径和
题目
- 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
- 说明:每次只能向下或者向右移动一步。
- 输入:
1
2
3
4
5[
[1,3,1],
[1,5,1],
[4,2,1]
] - 输出: 7
- 解释: 因为路径 1→3→1→1→1 的总和最小。
- link
解题思路
- 思路明显,二维数组动态规划
- dp[ i ][ j ]:从起点到达 (i , j)位置的路径和
- dp[ i ][ j ] = Math.min(dp[ i ][j-1], dp[ i-1 ][ j ]) + grid[i][j];
- 只用到了左边和上边的位置,所以可以优化到一维数组
- 初始状态,i=0 以及 j = 0,第0行和第0列的初始化
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public int minPathSum(int[][] grid) {
if(grid.length == 0) return 0;
int dp[] = new int [grid[0].length];
dp[0] = grid[0][0];
for(int i = 1 ; i < dp.length; i++){
dp[i] = dp[i-1] + grid[0][i];
}
for(int i = 1; i<grid.length; i++){
dp[0] += grid[i][0];
for(int j = 1; j<dp.length; j++){
dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];
}
}
return dp[dp.length-1];
} - 复杂度分析
- 时间复杂度O(N*M)
- 空间复杂度O(M)
28. 编辑距离
题目
- 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。
- 你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
- 输入:word1 = “horse”, word2 = “ros”
- 输出:3
- 解释:
1
2
3horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e') - link
解题思路
- 动态规划解题
- 求最优解问题
- 是可以分阶段进行的
- 每个阶段有插入、删除、替换三个选择
- 插入、删除、替换设定都在末尾进行
- 等价的,在中间插入也是可以转换到尾部操作的
- 最优子结构
- dp[ i ][ j ],表示将word1的前 i 位 转换成 word2的前 j 位需要的最少操作数
- 它可以通过三种方式获得,且取三种方式中的最小值
- word1末尾插入
- dp[ i ][ j ] = dp[ i-1 ][ j ] + 1;
- hors -> ros 需要a步,则horse -> ros 需要 a+1 步
- word1末尾删除
- dp[ i ][ j ] = dp[ i ][ j-1 ] + 1;
- hors -> ro需要 b 步,则 hors -> ros 需要 b+1 步
- word1末尾替换
- dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1 ,如果 i 和 j 字符不同, 则需要额外一次替换操作
- hors - > ro 为 c, 则horo -> ro需要额外一次替换操作
- dp[ i ][ j ] = dp[ i-1 ][ j ] , 如果 i 和 j 字符相同,则不需要额外一次操作
- hor -> ro 为 d ,则 hors -> ros 为 d
- dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1 ,如果 i 和 j 字符不同, 则需要额外一次替换操作
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27public int minDistance(String word1, String word2) {
int len1 = word1.length(), len2 = word2.length();
if(len1 == 0) return len2;
if(len2 == 0) return len1;
int dp[][] = new int [len1 +1 ][len2+1];
for(int i = 0; i <= len1; i++ ){
dp[i][0] = i;
}
for(int i = 0; i<= len2; i++){
dp[0][i] = i;
}
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; j++){
int insert = dp[i-1][j] + 1;
int remove = dp[i][j-1] + 1;
int replace = 0;
if(word1.charAt(i-1) == word2.charAt(j-1)){
replace = dp[i-1][j-1];
}else{
replace = dp[i-1][j-1] + 1;
}
dp[i][j] = Stream.of(insert,remove, replace)
.min(Comparator.comparing(Integer::valueOf)).get();
}
}
return dp[len1][len2];
} - 复杂度分析
- 时间复杂度O(M*N)
- 空间复杂度O(M*N)
29. 颜色排序
题目
- 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
- 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
- 不能使用代码库中的排序函数来解决这道题。
- 输入: [2,0,2,1,1,0]
- 输出: [0,0,1,1,2,2]
- 进阶
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
- 首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
- 你能想出一个仅使用常数空间的一趟扫描算法吗?
- 题目地址
解题思路
思路1:计数排序算法
- 计数排序
- 数组统计各种元素的出现频数
- 对频数数组进行连续累加,对应的数字便是该类值插入位置的后一个
- 读取原数组中的数字,并查找频数数组,确定插入的位置
- 插入成功之后,频数数组对应的值-1
- 即,插入位置前移一个
- 这里由于只要对值排序就可以,相同的值之间没有差异,所以得到频数数组之后,直接更改原数组即可
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14public void sortColors(int[] nums) {
int[] count = new int[3];
for (int i = 0; i < nums.length; i++) {
count[nums[i]]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
for (int j = 0; j < count[i]; j++) {
nums[index] = i;
index++;
}
}
} - 复杂度分析
- 时间复杂度O(K+N)
- 空间复杂度O(K)
思路2:双指针算法
- 类似三路排序的效果,能够高效处理含有大量重复元素的情况
- 一路指针标记0的插入位置,另一路标记2的插入位置,0和2排序好了,中间剩下的1便也排序好了
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public void sortColors(int[] nums) {
int left = 0, right = nums.length - 1;
int index = left;
while (index <= right) {
if (nums[index] == 0) {
swap(nums, index, left);
left++;
index++;
} else if (nums[index] == 2) {
swap(nums, index, right);
right--;
} else {
index++;
}
}
} - 复杂度分析
- 时间复杂度O(N)
- 空间复杂度O(1)
30.最小包含子串
题目
- 给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。
- 输入: S = “ADOBECODEBANC”, T = “ABC”
- 输出: “BANC”
- 如果 S 中不存这样的子串,则返回空字符串 “”。
- 如果 S 中存在这样的子串,我们保证它是唯一的答案。
- link
解题思路
- 滑动窗口解题的典型例题
- T字符中可能存在重复字符
- 对字符进行计数
- 可以使用数组统计128所有字符
- 也可以通过HashMap,只统计出现的字符
1
2
3
4
5
6
7for (char c : tValues) {
if (tMap.containsKey(c)) {
tMap.put(c, tMap.get(c) + 1);
} else {
tMap.put(c, 1);
}
}
- 检测当前窗口是否包含T所有字符
- distance,即窗口内容与T之间的距离
- 当字符出现在T中,且该字符能缩小窗口与T距离的时候,distance++
1
2
3
4
5
6
7
8
9
10// 字符在t中,更改distance
if (winMap.containsKey(sValues[right])) {
if (winMap.get(sValues[right]) < tMap.get(sValues[right])) {
distance++;
}
winMap.put(sValues[right], winMap.get(sValues[right]) + 1);
} else {
winMap.put(sValues[right], 1);
distance++;
}
- 思路与过程
- 通过HashMap,统计T字符串中字符的出现次数
- left,right=0,窗口从左出发
- 先right右移,right位置元素未在TMap中,则继续右移
- 当right位置元素出现在TMap中
- 如果SMap中该字符数目 < TMap中该字符数目
- distance++
- 说明该字符能有效降低窗口和T之间的距离
- 若大于等于,说明该元素重复了
- 然后SMap中该字符数目+1
- 如果SMap中该字符数目 < TMap中该字符数目
- 检测distance
- 如果比T的长度小,则right继续右移
- 如果和T长度相等,说明当前窗口是满足包含所有T字符的子串,但需要缩小到最小子串
- left指针右移
- 移动到distance不等于T长度为止
- 判断left位置字符是否出现在TMap中
- 出现,若SMap中该字符频数 <= TMap中该字符频数,distance–
- SMap中该字符频数-1
- 最终left的位置便是子串最左位置的下一个
- length = right -left +2
- 更新最短长度以及其实位置
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60public String minWindow(String s, String t) {
char[] sValues = s.toCharArray();
char[] tValues = t.toCharArray();
int left = 0, right = 0;
HashMap<Character, Integer> tMap = new HashMap<>();
HashMap<Character, Integer> winMap = new HashMap<>();
int distance = 0;
int minBegin = 0, minLength = Integer.MAX_VALUE;
for (char c : tValues) {
if (tMap.containsKey(c)) {
tMap.put(c, tMap.get(c) + 1);
} else {
tMap.put(c, 1);
}
}
while (right < sValues.length) {
// right 右移
if (!tMap.containsKey(sValues[right])) {
// 字符不在t中,right右移
right++;
continue;
}
// 字符在t中,更改distance
if (winMap.containsKey(sValues[right])) {
if (winMap.get(sValues[right]) < tMap.get(sValues[right])) {
distance++;
}
winMap.put(sValues[right], winMap.get(sValues[right]) + 1);
} else {
winMap.put(sValues[right], 1);
distance++;
}
if (distance < t.length()) {
right++;
continue;
}
// 判断distance,等于t串长度的时候,left开始左移
while (distance == t.length()) {
if (winMap.containsKey(sValues[left])) {
if (winMap.get(sValues[left]) <= tMap.get(sValues[left])) {
distance--;
}
winMap.put(sValues[left], winMap.get(sValues[left]) - 1);
}
left++;
}
// 最终,left为满足条件的左边界的下一个
if (right - left + 2 < minLength) {
minBegin = left - 1;
minLength = right - left + 2;
}
right++;
}
if (minLength == Integer.MAX_VALUE) {
return "";
}
return s.substring(minBegin, minBegin + minLength);
} - 复杂度分析
- 时间复杂度O(N+M)
- 空间复杂度O(N+M)
下个路口见
HOT100依然在继续,写在下一篇文章中。传送门