首页 > 试题广场 >

最长无重复子数组

[编程题]最长无重复子数组
  • 热度指数：343578 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

数据范围：，
示例1

输入

[2,3,4,5]

输出

4

说明

[2,3,4,5]是最长子数组
示例2

输入

[2,2,3,4,3]

输出

3

说明

[2,3,4]是最长子数组
示例3

输入

[9]

输出

1
示例4

输入

[1,2,3,1,2,3,2,2]

输出

3

说明

最长子数组为[1,2,3]
示例5

输入

[2,2,3,4,8,99,3]

输出

5

说明

最长子数组为[2,3,4,8,99]
算法知识视频讲解
添加回答
C/C++
一个好听的名字头像 一个好听的名字 
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;
    }
};

发表于 2020-12-16 21:10:44 回复(0)
pisway头像 pisway
//之前创建了set 显示超时，改用位子标记 部分查找 不增加变量的存储
int maxLength(vector<int>& arr) {
       int res(0);
    int counter(0);
    for(auto i = arr.begin(); i != arr.end(); i++)
    {
        counter = 0;
        for(auto t = i; t != arr.end(); t++)
        {
            if(find(i,t,*t) != t)
            {
                res = max(res, counter);
                break;
            }
            else
            {
                counter++;
            }
        }
        res = max(res, counter);
    }
    return res;
    }
发表于 2020-12-21 10:21:48 回复(0)
Java
触初头像 触初
5种解法 

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



发表于 2022-05-06 22:05:50 回复(1)
Python 3
henryboy233头像 henryboy233 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @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
                
                
                
                

发表于 2021-12-14 22:01:50 回复(0)
Javascript
牛客648389563号头像 牛客648389563号
function maxLength( arr ) {
    // write code here
    let startIdx = 0;
    let endIdx = arr.length - 1;
    let resArr = [];
    while(startIdx <= endIdx) {
        let curArr = [];
        for(let i = startIdx; i< arr.length; i++){
              const isFind = curArr.indexOf(arr[i]);
            if(isFind > -1) {
                if(resArr.length < curArr.length) {
                    resArr = [...curArr];
                }
                startIdx = startIdx + isFind + 1;
                curArr = [];
                break;
            } else {
                curArr.push(arr[i])
                if(i === endIdx) {
                    startIdx = endIdx + 1;
                     if(resArr.length === 0) {
                        resArr = [...curArr];
                    }
                }
            }
        }
        
    }
   return resArr.length;
}
发表于 2021-11-03 14:47:02 回复(0)
C++
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
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;
  }
};

发表于 2021-10-20 14:03:42 回复(0)
Java
一只小牛蛙🐸头像 一只小牛蛙🐸 
    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;
    }

发表于 2021-09-09 17:25:46 回复(0)
Javascript
黄棉头像 黄棉
/**
 *
 * @param arr int整型一维数组 the array
 * @return int整型
 */
function maxLength( arr ) {
    // write code here
    let leftPoint = 0
    let rightPoint = 0
    let len = 0
    let maxLen = 0
    let flag = false
    let obj = {}
    if(arr.length === 0) {
        return 0
    }
    while(rightPoint <= arr.length) {
        if(obj[arr[rightPoint]] !== undefined) {
            if(!flag){flag= true}
            len = rightPoint - leftPoint
            maxLen = Math.max(maxLen, len)
            leftPoint = obj[arr[rightPoint]] + 1
            rightPoint = leftPoint
            obj = {}
        } else {
            obj[arr[rightPoint]] = rightPoint++
        }
    }
    if(flag){
        return maxLen
    } else {
        return arr.length
    }
}
module.exports = {
    maxLength : maxLength
};

还可以完善，先就这样
发表于 2021-08-20 16:24:05 回复(0)
Java
肿肿的肿头像 肿肿的肿
思路：分配一个List来存放子数组，遍历数组，当子数组中包含当前元素的时候，判断当前子数组是不是最大，然后把子数组置空，存放下一轮的子数组。如下：

public int maxLength (int[] arr) {
        // write code here
        
        if(arr==null||arr.length==0){
            return 0;
        }
        
        int max = Integer.MIN_VALUE;
        List subList = new ArrayList();
        
        for(int i=0;i<arr.length;i++){
            if(subList.contains(arr[i])){
                max = Math.max(max,subList.size());
                subList = new ArrayList();
            }
            subList.add(arr[i]);
        }
        max = Math.max(max,subList.size());
        return max;
    }

可是为什么通不过？？？
发表于 2021-08-04 11:06:01 回复(1)
OneToN头像 OneToN 
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;
    }
}
发表于 2021-07-05 11:01:08 回复(0)
杨雪dph头像 杨雪dph 
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;
    }
}
}
思路：
1.两种特殊情况：数组为空或数组长度为一，解是定值；
2.一般情况：需要两个指针。一个指向头，一个指向头指针开始到出现重复值的指针。两个指针之间的长度为返回值。
如何判断是否重复？用map。放入数组数据，如果出现重复，则停止，map的长度也为返回值。
如何存储最大值？Math.max(maxlength,new)
发表于 2021-06-04 16:27:40 回复(0)
Mono_Chrome头像 Mono_Chrome 
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;
    }
}
发表于 2021-05-19 18:48:38 回复(0)
杨超越保佑我🙏头像 杨超越保佑我🙏 
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)

发表于 2021-05-14 16:20:13 回复(0)
不打工就没饭吃喔头像 不打工就没饭吃喔
  • 滑动窗口，用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;
}
发表于 2021-05-07 12:16:21 回复(0)
Java
弹指間头像 弹指間
采用滑动窗口，利用数组判断是否重复 
import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        //由题可知数据范围，1≤n≤100000，这样判断是否重复所需时间为O(1)
        byte[] freq = new byte[100000];
        //滑动窗口双指针
        int l=0, r=-1;
        //最长无重复子串
        int res=0;
        while(l<arr.length){
            //如果 r+1不越界，对应值且没有重复的标记，则 r++
            if(r+1<arr.length && freq[arr[r+1]]==0){
                r++;
                freq[arr[r]]++;
            }else{
                //否则 不断缩小左边界（l++），相应标记复位
                freq[arr[l]]--;
                l++;
            }
            //判断窗口大小是否需要更改
            res=Math.max(res,r-l+1);
        }
        return res;
    }
}


发表于 2021-03-25 22:52:57 回复(0)
小吴..头像 小吴..
滑动窗口 
import java.util.*;

public class Solution {
    public int maxLength (int[] arr) {
        int len = arr.length;
        int left = 0;
        int right = 0;
        int res = 0;
        boolean valid = false;     // 表示窗口是否满足无重复元素
        HashMap<Integer, Integer> map = new HashMap<>();     // 窗口中各个数字出现的情况，key：数字，value：该数出现的次数
        while (right < len) {
            int add = arr[right];
            right++;
            map.put(add, map.getOrDefault(add, 0) + 1);
            if (map.get(add) == 1) {    // 判断该数是否只出现一次
                valid = true;
            } else {
                valid = false;
            }

            // 缩小窗口
            while (!valid) {
                int remove = arr[left];
                map.put(remove, map.get(remove) - 1);
                if (map.get(remove) == 1){    // 如果该数出现的次数减为1则窗口满足条件
                    valid = true;
                }
                left++;
            }
            // 更新结果
            res = Math.max(res, right - left);
        }
        return res;
    }
}


发表于 2021-02-22 23:17:30 回复(0)
C/C++
BrainerGao头像 BrainerGao 
/**
 * 
 * @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;
}

发表于 2021-02-21 15:36:32 回复(0)
C/C++
cn_LittleYu头像 cn_LittleYu 
class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        std::map<int, int> tmp;
        int result = 0;
        for (int i = 0; i < arr.size();) {
            auto iter = tmp.find(arr[i]);
            if (iter != tmp.end()) {
                i = iter->second + 1;
                if (tmp.size() > result) {
                    result = tmp.size();
                }
                tmp.clear();
            } else {
                tmp.insert(std::make_pair(arr[i], i));
                ++i;
            }
        }
        return result;
    }
};
面试小米的时候，面试官出的题目。
朴素的方法，就是拿个临时的空间去记录串，向后遍历arr，查看值是否在串中出现。
出现了就比较最大值和临时空间里的数据谁大，然后清空临时空间，下标跑回去；没有出现就把值扔到临时空间里。

我考虑优化的点，就是不想让下标往回跑太多，跑太多实际上是无意义的，正好跑到重复值的后一个下标就好。所以这里很蛋疼的用了个map来记录值和下标。

注：STL可能会影响性能，主要是写的省事，习惯用STL了，又没有什么打比赛的需求。（逃
发表于 2021-01-15 20:24:16 回复(6)
Midp头像 Midp 
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;
    }
}

发表于 2020-09-23 16:01:34 回复(0)
Java
中南的小菜鸡头像 中南的小菜鸡 
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;
    }
}

发表于 2020-09-19 15:11:00 回复(1)
提交观点

问题信息

数组 哈希 双指针
难度：
449条回答 20190浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长无重复子数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号