3
#yyds干货盘点# 面试必刷TOP101：最长无重复子数组
source link: https://blog.51cto.com/u_15488507/5766760
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 面试必刷TOP101：最长无重复子数组
精选 原创1.简述：
描述
给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
数据范围：，
示例1
[2,3,4,5]
[2,3,4,5]是最长子数组
示例2
[2,2,3,4,3]
[2,3,4]是最长子数组
示例3
示例4
[1,2,3,1,2,3,2,2]
最长子数组为[1,2,3]
示例5
[2,2,3,4,8,99,3]
最长子数组为[2,3,4,8,99]
2.代码实现：
import java.util.*;
public class Solution {
public int maxLength (int[] arr) {
//哈希表记录窗口内非重复的数字
HashMap<Integer, Integer> mp = new HashMap<>();
int res = 0;
//设置窗口左右边界
for(int left = 0, right = 0; right < arr.length; right++){
//窗口右移进入哈希表统计出现次数
if(mp.containsKey(arr[right]))
mp.put(arr[right],mp.get(arr[right])+1);
else
mp.put(arr[right],1);
//出现次数大于1，则窗口内有重复
while(mp.get(arr[right]) > 1)
//窗口左移，同时减去该数字的出现次数
mp.put(arr[left],mp.get(arr[left++])-1);
//维护子数组长度最大值
res = Math.max(res, right - left + 1);
}
return res;
}
}
public class Solution {
public int maxLength (int[] arr) {
//哈希表记录窗口内非重复的数字
HashMap<Integer, Integer> mp = new HashMap<>();
int res = 0;
//设置窗口左右边界
for(int left = 0, right = 0; right < arr.length; right++){
//窗口右移进入哈希表统计出现次数
if(mp.containsKey(arr[right]))
mp.put(arr[right],mp.get(arr[right])+1);
else
mp.put(arr[right],1);
//出现次数大于1，则窗口内有重复
while(mp.get(arr[right]) > 1)
//窗口左移，同时减去该数字的出现次数
mp.put(arr[left],mp.get(arr[left++])-1);
//维护子数组长度最大值
res = Math.max(res, right - left + 1);
}
return res;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK