本文主要是介绍小白教你最长无重复子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最长无重复子数组
题目描述：
给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
示例：
输入：[2,3,4,5]
返回值:4
说明：[2,3,4,5]是最长子数组
题目链接：
最长无重复子数组
思路：
小白起初看这道题首先想到的是这个题需要使用set集合。
然后小白先想到的是暴力求解，也就是把该数组的每一个位置的最长无重复子数组计算出来，然后返回最大值。我们直接来看一下代码。
import java.util.*;
public class Solution {public int maxLength (int[] arr) {// write code hereint res = 0;//最大长度for (int i = 0; i < arr.length; i++) {int count = 0;//第arr[i]位置开始的最长无重复数的长度int flag = i;//记录当前i值HashSet<Integer> set = new HashSet<Integer>();//set用来判断数组是否出现重复while (flag < arr.length && !set.contains(arr[flag])) {count++;set.add(arr[flag]);//此时子数组无重复值，将该值加入set集合中if (count > res) {res = count;}flag++;}}return res;}
}
上面这个方法不好，时间复杂度很高的同时浪费了很多的空间。但上面这个让我们打好了优化代码的基础。
现在我们在换一种思路，我们现在设置两个指针。
一个指针left，一个指针right初始时均指向arr[0]处，
在left与right不超过数组长度的前提下我们做以下操作：
①判断arr[right]是否是在set集合中，没在的话right右移一位，将该值加入set集合中，并判断此时set集合中的size（）是否大于我们起初设置的res。
②如果arr[right]在set集合中，我们将set集合中的arr[right]remove,并把left向右移一位。
③重复①②，返回最大res。
代码：
import java.util.*;public class Solution {/*** * @param arr int整型一维数组 the array* @return int整型*/public int maxLength (int[] arr) {// write code hereint res = 0;//存储最大子数组数值HashSet<Integer> set = new HashSet<Integer>();int left = 0;//左指针int right = 0;//右指针while (right < arr.length) {if (!set.contains(arr[right])) {set.add(arr[right]);right++;if (set.size() > res) {res = set.size();}}else {set.remove(arr[left]);left++;}}return res;}
}
这篇关于小白教你最长无重复子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
