最长无重复子数组

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;
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @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;
    }

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 {
    /**
     * 
     * @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;
    }
}

• 滑动窗口，用set维护一个不重复的窗口

  /* 滑动窗口，用set维护一个不重复的窗口 */
  public int maxLength (int[] arr) {
    int res = 0;
    Set<Integer> set = new HashSet<>();
    for(int l = 0, r = 0; r < arr.length; r++) {
        int a = arr[r];
        while(set.contains(a)) {
            set.remove(arr[l++]);
        }
        set.add(a);
        res = Math.max(res, r - l + 1);
    }
    return res;
  }

/**
 * 
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return int整型
 */
int maxLength(int* arr, int arrLen ) {
    int n[100000] = {0};
    int left = 0;
    int right = 0;
    int res = 0;
    while (right < arrLen) {
        if (n[arr[right]] > 0) {
            n[arr[left]] = 0;
            left++;
        } else {
            n[arr[right]] = 1;
            res = res > right - left + 1 ? res : right - left + 1;
            right++;
        }
    }
    return res;
}

import java.util.*;
public class Solution {
    public int maxLength (int[] arr) {
        if(arr.length<2) return arr.length;
        // write code here
        Stack<Integer> stack = new Stack<>();
        int res_lat = 0;
        for(int i=0;i<arr.length;i++){
            int pre =stack.search(arr[i]);
            int lat =stack.size()-stack.search(arr[i])+1;
            if(pre==-1){
                stack.push(arr[i]);
                res_lat=res_lat>stack.size()?res_lat:stack.size();
            }else{
                 res_lat=res_lat>stack.size()?res_lat:stack.size();
                for(int j=0;j<lat;j++){
                    stack.remove(0);
                }
                stack.push(arr[i]);
            }
        }
        return res_lat;
    }
}

import java.util.*;

public class Solution {
    /**
     * 有点类似滑动窗口，从左到右遍历，遇到重复的，找到重复的索引，左指针++
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        int start = 0;
        int end = -1;
        int maxLen = 0;
        Map<Integer,Integer> map  = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i]) && map.get(arr[i]) >= start) {
                start = map.get(arr[i]) + 1;
            }
            map.put(arr[i],i);
            end++;
            if (end-start+1>maxLen){
                maxLen = end-start+1;
            }
        }
        return maxLen;
    }
}

class Solution {
public:
    int maxLength(vector<int>& arr) {
        // write code here
        int m[40000] = {0};//用map更好
        unsigned int ans = 1, l = 0;//l记录重复位置
        arr.push_back(arr[arr.size() - 1]);//尾部添加一个重复数据使其必然触发(3)条件
        for(int i = 0; i < arr.size(); ++i){
            if(m[arr[i]]){// （3）
                if(ans < i - l)
                     ans = i - l;
                if(m[arr[i]] > l)//只需在重复时记录下重复数据的位置
                    l = m[arr[i]];
            }
            m[arr[i]] = i + 1; 
        }
        return ans;
    }
};

class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        int l = 0, r = 0, ans = 0;;
        set<int> s;
        while (r < arr.size()) {
            if (!s.count(arr[r])) {
                s.insert(arr[r++]);
            } else{
                s.erase(arr[l++]);
            }
            ans = ans > s.size() ? ans : s.size();
        }
        return ans;
    }
};