给定一个长度为n的数组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]
class Solution { public: /** * * @param arr int整型vector the array * @return int整型 */ int maxLength(vector<int>& arr) { map<int, int> num_index; //检查是否越界了的map工具 map<int, int>::iterator iter; //迭代器 int before = 0; int after = 1; int max_len = 1; int arr_len = arr.size(); num_index[arr[0]] = 0; int temp_len = 1; int next_before = 0; //下面开始在线的动态测量过程 for (after = 1; after < arr_len; after++) { if (before > arr_len - max_len) //设置一个判断是否可以直接终止的情况,为了节省时间 break; iter = num_index.find(arr[after]); //判断是否在当前的map中 if (iter == num_index.end()) //当前集合没有该键值对 { num_index[arr[after]] = after; //匹配该值和所在的位置索引值 temp_len++; } else //当前集合存在该键值对,重复了 { next_before = iter->second; if (temp_len > max_len) //更新最大长度值 { max_len = temp_len; } temp_len = after - next_before; if (next_before - before < after - next_before) //map删除前面的,保留后面的,最后再加上一个after { for (int i = before; i <= next_before; i++) //一个一个删除前面的部分 { num_index.erase(arr[i]); } num_index[arr[after]] = after; } else //直接清空map,从next_before往后一个一个加进来,加到after { num_index.clear(); for (int i = next_before + 1; i <= after; i++) { num_index[arr[i]] = i; } } before = next_before + 1; } } if (temp_len > max_len) max_len = temp_len; return max_len; } };
public int maxLength (int[] arr) { int count=0; LinkedList<Integer> list= new LinkedList<>(); for(int i=0;i<arr.length;i++) { if(list.contains(arr[i])) { for(int j=list.indexOf(arr[i]);j>=0;j--) { list.removeFirst(); } } list.add(arr[i]); count=Math.max(count,list.size()); } return count;
import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; /** * NC41 最长无重复子数组 */ public class Solution41 { /** * @param arr int整型一维数组 the array * @return int整型 */ public int maxLength(int[] arr) { // write code here HashSet<Integer> set = new HashSet<>(); int l = 0; int r = 0; int max = 0; while (r < arr.length) { if (!set.contains(arr[r])) { set.add(arr[r++]); } else { while (arr[l] != arr[r]) { set.remove(arr[l++]); } set.remove(arr[l++]); } max = Math.max(max, set.size()); } return max; } public int maxLength1(int[] arr) { // write code here HashSet<Integer> set = new HashSet<>(); int l = 0; int r = 0; int max = 0; while (r < arr.length) { while (set.contains(arr[r])) { set.remove(arr[l++]); } set.add(arr[r++]); max = Math.max(max, set.size()); } return max; } public int maxLength2(int[] arr) { // write code here Queue<Integer> queue = new LinkedList<>(); int max = 0; for (int num : arr) { while (queue.contains(num)) { queue.poll(); } queue.add(num); max = Math.max(max, queue.size()); } return max; } public int maxLength3(int[] arr) { // write code here 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; } public int maxLength4(int[] arr) { // write code here HashMap<Integer, Integer> map = new HashMap<>(); int max = 0; for (int i = 0, j = 1; i < arr.length; i++) { j = Math.min(j + 1, i - map.getOrDefault(arr[i], -1)); max = Math.max(max, j); map.put(arr[i], i); } return max; } public static void main(String[] args) { Solution41 solution41 = new Solution41(); System.out.println(solution41.maxLength(new int[]{2, 2, 3, 4, 3})); System.out.println(solution41.maxLength1(new int[]{2, 2, 3, 4, 3})); System.out.println(solution41.maxLength2(new int[]{2, 2, 3, 4, 3})); System.out.println(solution41.maxLength3(new int[]{2, 2, 3, 4, 3})); System.out.println(solution41.maxLength4(new int[]{2, 2, 3, 4, 3})); } }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param arr int整型一维数组 the array # @return int整型 # class Solution: def maxLength(self , arr: List[int]) -> int: # write code here pre_dis = 0 maxl = 0 dis = {} for i in range(len(arr)): num = arr[i] if num in dis: pre_dis = max(pre_dis,dis[num]) maxl = max(maxl,i+1-pre_dis) dis[num]=i+1 return maxl
class Solution { public: /** * * @param arr int整型vector the array * @return int整型 */ int maxLength(vector<int>& arr) { // corner case if (arr.empty()) return 0; int ans = 0, start = 0; unordered_map<int, int> last; for (int i = 0; i < arr.size(); ++i) { if (last.find(arr[i]) != end(last) && last[arr[i]] >= start) start = last[arr[i]] + 1; ans = max(ans, i - start + 1); last[arr[i]] = i; } return ans; } };
public int maxLength (int[] arr) { // write code here if (arr == null || arr.length == 0) return 0; Set<Integer> set = new LinkedHashSet<>(); int index = 0; //记录最长无重复子数组的开始索引 int max = 0; for (int i = 0; i < arr.length; i++) { while (set.contains(arr[i])) { set.remove(arr[index++]); //存在重复的就从index开始删除,直至不含arr[i] } set.add(arr[i]); //添加arr[i] max = Math.max(max, i - index + 1); //取最大值 } return max; }
class Solution: def maxLength(self , arr ): # write code here record=[0]*len(arr) record[0]=1 for i in range(1,len(arr)): compare=arr[i-record[i-1]:i] if arr[i] in compare: #record[i]=record[i-1]-(len(compare)-compare[::-1].index(arr[i])-1) #化简后: record[i]=compare[::-1].index(arr[i])+1 else: record[i]=record[i-1]+1 return max(record)
class Solution: def maxLength(self , arr ): maxlen=0 stack=[] for i in arr: while i in stack: stack.pop(0) stack.append(i) maxlen=max(maxlen,len(stack)) return maxlen暴力法
int maxLength(vector<int>& arr) { int maxlength=0; int left=0,right=0; unordered_map<int,int> map1; map1.clear(); for(int i=0;i<arr.size();i++) { auto iter=map1.find(arr[i]); if(iter==map1.end()) { right++; map1.insert(make_pair(arr[i],i)); } else if(iter->second<left) { right++; map1[arr[i]]=i; } else { maxlength=max(maxlength,right-left); left=iter->second+1; map1[arr[i]]=i; right++; } } return max(maxlength,right-left); }
# # # @param arr int整型一维数组 the array # @return int整型 # class Solution: def maxLength(self , arr ): # write code here list_tem = [] num_max,tf = 0,1 for i in arr: if i not in list_tem: list_tem.append(i) else: num_max = max(len(list_tem),num_max) while i in list_tem: list_tem.pop(0) list_tem.append(i) tf = 0 if tf == 1: return len(list_tem) else: return num_max
import java.util.*; public class Solution { /** * * @param arr int整型一维数组 the array * @return int整型 */ public int maxLength (int[] arr) { // write code here int n = arr.length; int start = 0, end = 0; int max = 0; while (start <= end && end < n) { Set<Integer> set = new HashSet<>(); while (end < n && set.add(arr[end])) { if (end == n - 1) break; end++; } max = Math.max(max, set.size()); if (end == n - 1) break; start = end; } return max; } }
public class Solution { /** * * @param arr int整型一维数组 the array * @return int整型 */ public int maxLength (int[] arr) { // write code here int max = 0 ; int start = 0 ; Map<Integer,Integer> repeatIndex = new HashMap(); for (int i = 0 ;i < arr.length;i++){ if(repeatIndex.containsKey(arr[i])){ int repeatNumIndex = repeatIndex.get(arr[i]); start = Math.max(repeatNumIndex+1,start); } repeatIndex.put(arr[i],i); int curLength = i - start+1; max = Math.max(max,curLength); } return max; } }
import java.util.*; public class Solution { public int maxLength (int[] arr) { // write code here if(arr == null){ return 0; }else if(arr.length == 1){ return 1; } int maxlength = 1; for(int i = 0 ;i < arr.length;i ++){ Map<Integer,Integer> map = new HashMap(); int j = i; while(j < arr.length && !map.containsKey(arr[j])){ map.put(arr[j],0); j ++; }; maxlength =Math.max(maxlength,map.size()); } return maxlength; } } }
import java.util.*; public class Solution { /** * * @param arr int整型一维数组 the array * @return int整型 */ public int maxLength (int[] arr) { // write code here int[] map = new int[100001]; int left = 0; int right = 0; int res = 0; while (right < arr.length) { int cur = arr[right++]; map[cur]++; while (map[cur] > 1) { int del = arr[left++]; map[del]--; } res = Math.max(res, right - left); } return res; } }
python 利用二分法,不断判断左右两边和整串最大字串 class Solution: def maxLength(self , arr ): def sove(arr, start, end): if start == end-1 and arr[start] == arr[end]: return 1 if start == end-1: return 2 if start == end: return 1 mid = (start+end)//2 left = sove(arr, start, mid) right = sove(arr, mid+1, end) # flag = arr[mid] num = 1 index = mid for i in range(mid-1, start-1, -1): if arr[i] not in arr[i+1:mid+1]: num+=1 index = i else: break for j in range(mid+1, end+1): if arr[j] not in arr[index:j]: num+=1 else: break return max(num, left, right) return sove(arr, 0, len(arr)-1)