给定一个数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。
子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
输入:
[2,3,4,5]
返回值:
4
说明:
[2,3,4,5]是最长子数组
输入:
[2,2,3,4,3]
返回值:
3
说明:
[2,3,4]是最长子数组
输入:
[9]
返回值:
1
输入:
[1,2,3,1,2,3,2,2]
返回值:
3
说明:
最长子数组为[1,2,3]
输入:
[2,2,3,4,8,99,3]
返回值:
5
说明:
最长子数组为[2,3,4,8,99]
import java.util.*; public class Solution { /** * * @param arr int整型一维数组 the array * @return int整型 */ public int maxLength(int[] arr) { //用链表实现队列,队列是先进先出的 Queue<Integer> queue = new LinkedList<>(); int res = 0; for (int c : arr) { while (queue.contains(c)) { //如果有重复的,队头出队 queue.poll(); } //添加到队尾 queue.add(c); res = Math.max(res, queue.size()); } return res; } }
public int maxLength(int[] arr) { if (arr.length == 0) return 0; HashMap<Integer, Integer> map = new HashMap<>(); int max = 0; for (int i = 0, j = 0; i < arr.length; ++i) { if (map.containsKey(arr[i])) { j = Math.max(j, map.get(arr[i]) + 1); } map.put(arr[i], i); max = Math.max(max, i - j + 1); } return max; }