首页 > 试题广场 >

最长无重复子数组

[编程题]最长无重复子数组
  • 热度指数：361841 时间限制：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]
算法知识视频讲解
添加回答
Java
厚之同学头像 厚之同学 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        int len = 0;
        for (int i = 0; i < arr.length; i++) {
            Set<Integer> set = new HashSet<>();
            int j = i;
            while (j < arr.length && set.add(arr[j])) {
                j++;
            }
            len = Math.max(len, j - i);
        }
        return len;
    }
}

发表于 2025-09-29 09:53:53 回复(0)
Java
୧⍢⃝୨头像 ୧⍢⃝୨ 
import java.util.*;


public class Solution {
    public int maxLength (int[] arr) {
        int n = arr.length;

        Map<Integer, Integer> map = new HashMap<>();

        int res = 0;

        int i = 0;
        int j = 0;
        while (j < n) {
            map.put(arr[j], map.getOrDefault(arr[j], 0) + 1);

            if (j - i + 1 == map.size()) {
                res = Math.max(res, j - i + 1);
            }

            while (map.size() < j - i + 1) {
                map.put(arr[i], map.get(arr[i]) - 1);
                if (map.get(arr[i]) == 0) {
                    map.remove(arr[i]);
                }
                i++;
            }
            j++;
        }

        return res;
    }
}

发表于 2024-09-14 12:17:36 回复(0)
Java
洒脱的斜杠青年求求offer头像 洒脱的斜杠青年求求offer
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        HashSet<Integer> visited = new HashSet<>();
        int maxSeq = 1;
        for (int i = 0; i < arr.length; i++) {
            visited.add(arr[i]);
            for (int j = i + 1; j < arr.length; j++) {
                if (!visited.contains(arr[j])) {
                    visited.add(arr[j]);
                    if (visited.size() > maxSeq) {
                        maxSeq = visited.size();
                    }
                } else {
                    visited.clear();
                    break;
                }
            }
        }
        return  maxSeq;
    }
}
发表于 2024-07-23 17:34:42 回复(0)
Java
hakace头像 hakace 
    public static int maxLength(int[] arr) {
        int j = 0;
        int k = 1;
        Set<Integer> set = new HashSet<>();
        set.add(arr[0]);
        int max = 1;
        int current = 1;
        while (j < arr.length) {
            if (j + k >= arr.length || set.contains(arr[j + k])) {
                current = 1;
                set.clear();
                j++;
                if (j < arr.length) set.add(arr[j]);
                k = 1;
            } else {
                set.add(arr[j + k]);
                current++;
                k++;
            }
            max = Math.max(max, current);
        }
        return max;
    }
暴力
发表于 2024-07-03 15:51:27 回复(0)
Java
唐氏综合征头像 唐氏综合征
最优解，滑动窗口+双指针： 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] nums) {
        // write code here
        int n = nums.length;
        int left = 0, right = 0;
        int maxLength = 0;
        Set<Integer> uniqueElements = new HashSet<>();

        while (right < n) {
            if (!uniqueElements.contains(nums[right])) {
                uniqueElements.add(nums[right]);
                maxLength = Math.max(maxLength, right - left + 1);
                right++;
            } else {
                // 从最左边移除元素, 当移除掉重复元素时，left 刚好为重复元素下标 +1, 则可继续计算
                uniqueElements.remove(nums[left]);
                left++;
            }
        }

        return maxLength;
    }

}


编辑于 2024-04-12 22:04:04 回复(0)
Java
牛客276339250号头像 牛客276339250号
新建一个set记录字串
import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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 len=arr.length;
int max=Integer.MIN_VALUE;
while(r<len){
if(!set.contains(arr[r])){
当字符不在set中时，字符添加到set中并更新最大长度
set.add(arr[r]);
max=Math.max(max,set.size());
r++;
}else{
当set中存在字符时，说明字符已经重复需要删除重复的字符前的字符
set.remove(arr[l]);
l++;
}
}
return max;
}
}
发表于 2023-11-23 16:42:40 回复(0)
Java
懷戀，那弎年头像 懷戀，那弎年 
public class Solution {
    /**
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        Map<Integer, Integer> map = new HashMap<>();
        int left = 0, res = 1;
        map.put(arr[0], 0);
        for (int right = 1; right < arr.length; right++) {
            if (map.containsKey(arr[right])) {
                int temp = map.get(arr[right]);
                for (int i = left; i <= temp; i++) {
                    map.remove(arr[i]);
                }
                left = temp + 1;
            }
            map.put(arr[right], right);
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

发表于 2023-06-09 20:56:38 回复(0)
Java
牛客375488447号头像 牛客375488447号
记录以下自己逻辑漏洞的代码，代码逻辑为滑动窗口最大化，用一个int[]来记录滑动窗口中每个数出现的次数，index值为滑动窗口中的数，num值为出现的次数。
当走到下一个数时判断有没有在滑动窗口中，有的话证明重复，窗口边界都往后移一位，注意边界数的增删情况。保证int[]中只有滑动窗口的数记录。到达最后就能求出最大的窗口。 
import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        if(arr.length == 1){
            return 1;
        }
        int[] temp = new int[10000];//  // 记录出现的次数
        int start = 0; //  // 滑动窗口起始边界
        int end = 1; // // 滑动窗口终止边界
        temp[arr[start]] = 1; // 初始值记录
        while(end < arr.length){
            // 判断arr[end]这个数是否在被记录中
            if(temp[arr[end]] != 0){
                // 被记录先移除起始边界的值，起始边界向后移动
                temp[arr[start]] -=1;
                start++;
            }
            // 添加arr[end] 记录
            temp[arr[end]] +=1;
            // 终止边界移动
            end++;
        }
        // 最后得到的滑动窗口就是最大的那一个
        return end - start;
    }
}



执行到第八组错误，仔细回想逻辑中的漏洞，发现是只判断了最后一位是否有重复，其余在滑动窗口中的没判断导致出现这样的情况。就本次用例来看。
3 3 2 1 3 3 3 1  
3                             初始 start=0 end=1，接下来以滑动窗口中的数来展示
   3                          因为end=1的时候数被记录，所以整体移动，此时start=1  end=2
   3 2                       没有相同的数，end移动，start不移动，start=1 end = 3
   3 2 1                    没有相同的数，end移动，start不移动，start=1 end = 4
      2 1 3                 有相同，整体移动  start=2  end=5
         1 3 3              有相同，整体移动  start=3  end=6
            3 3 3           有相同，整体移动  start=4  end=7
            3 3 3 1       没有相同，因为一直判断的都是尾数与滑动窗口中的数 start=4 end=8
最后这一步错误，刚开始的的方法就想的这样，哎！！！！！
            
发表于 2023-05-26 11:22:55 回复(0)
Java
MorpheusNeo头像 MorpheusNeo 
import java.util.*;

public class Solution {
    /**
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        if (arr.length == 1) {
            return 1;
        }
        int maxLen = Integer.MIN_VALUE;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (!repeat(arr, i, j) && maxLen < (j - i + 1)) {
                    maxLen = (j - i + 1);
                }
            }
        }
        return maxLen;
    }

    public static boolean repeat(int[] arr, int start, int end) {
        Set<Integer> set = new HashSet<>();
        for (int idx = start; idx <= end; idx++) {
            set.add(arr[idx]);
        }
        return set.size() != (end - start + 1);
    }
}

发表于 2023-05-07 18:13:25 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public int maxLength (int[] arr) {
        //滑动窗口
        int left=0;
        int right=0;
        int max=0;
        Set<Integer> set=new HashSet<>();
        while(right<arr.length){
            if(!set.contains(arr[right])){
                set.add(arr[right]);
                right++;
            }else{
                set.remove(arr[left]);
                left++;
            }
            max=Math.max(max,set.size());
        }
        return max;
    }

发表于 2023-05-06 22:11:18 回复(0)
Java
阿阿阿阿K头像 阿阿阿阿K 
import java.util.*;

/**
*窗口右边一直后移，直到遇到set中包含的元素停止。然后窗口左边后移，set不断移除左端元素，
*直到把set中的重复元素移除，这时候窗口右边又可以继续移动啦，max记录最大窗口大小，循环往复。
*/
public class Solution {
    /**
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        if (arr.length == 0 || arr.length == 1) {
            return arr.length;
        }
        HashSet set = new HashSet();
        int low = 0, fast = 0;
        int max = 0;
        while(fast < arr.length){
            if(!set.contains(arr[fast])){
                    set.add(arr[fast++]);
                    max = Math.max(fast-low, max);
            }else{
                set.remove(arr[low++]);
            }
        }
        return max;
    }
}

发表于 2023-05-05 09:05:37 回复(0)
Java
进入人才池头像 进入人才池 
import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        int res = -1;
        // 滑动窗口
        int n = arr.length, l = 0, r = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // 右指针主动移动
        for ( r = 0; r < n; r++ ) {
            map.merge(arr[r], 1, Integer::sum);

            // 有重复
            while ( map.size() < r-l+1 ) {
                // 左指针右移
                int left = arr[l++];
                map.merge(left, -1, Integer::sum);
                if ( map.get(left) == 0 ) map.remove(left);
            }
            res = Math.max(res, r-l+1);    
        }
        return res;
    }
}

发表于 2023-04-25 11:41:32 回复(0)
Java
牛客725140028号头像 牛客725140028号
//hashset做
import java.util.*;

public class Solution {
    /**
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        int max = 0;
        int solution = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (set.contains(arr[j])) {
                    set.clear();
                    break;
                }
                set.add(arr[j]);
                max++;

            }
            solution = (solution > max) ? solution : max;
            max = 0;
        }

        return solution;
    }
}

发表于 2023-03-26 12:02:50 回复(0)
Java
BlueProtocol头像 BlueProtocol 
public class Solution {
    public int maxLength (int[] arr) {
        // write code here
        int max = 0;
        if (arr.length == 1) return 1;
        Queue<Integer> queue = new LinkedList();
        for ( int i = 0; i < arr.length; i++) {
            while (queue.contains(arr[i])) {
                queue.poll();
            }
            queue.add(arr[i]);
            max = Math.max(max,queue.size());
        }
        return max;

    }
}

发表于 2023-03-21 15:34:25 回复(1)
Java
wpcAlex头像 wpcAlex 
import java.util.*;


public class Solution {
    public int maxLength (int[] arr) {
        // write code here
        // 滑动窗口
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        //设置窗口左右边界
        for (int i = 0, j = 0; i < arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
            while (map.get(arr[i]) > 1) { //重复
                //窗口左侧右移，减去重复该数字的次数
                map.put(arr[j], map.get(arr[j++]) - 1);
            }
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
}


发表于 2023-01-28 14:13:32 回复(0)
Java
ludvig头像 ludvig
滑动窗口
import java.util.ArrayList;
import java.util.HashSet;

public class Solution {
    public int maxLength (ArrayList<Integer> arr) {
        HashSet<Integer> hashSet = new HashSet<>();
        int i = 0;
        int j = i;
        int maxLength = 0;
        while(j<arr.size() && i<=j){
            if(!hashSet.contains(arr.get(j))){
                hashSet.add(arr.get(j));
                j++;
            }else{
                hashSet.remove(arr.get(i));
                i++;
            }
            if(j-i>maxLength){
                maxLength = j-i;
            }
        }
        return maxLength;
    }
}


发表于 2022-09-28 00:44:50 回复(0)
Java
勇敢牛牛不怕难头像 勇敢牛牛不怕难 
import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        Map<Integer,Integer> map =new HashMap<>();
        int i=0;
        int j=0;
        int res=0;
        while(j<arr.length){
                while(map.containsKey(arr[j])){
                    map.remove(arr[i]);
                    i++;
                } 
                res=Math.max(res,j-i+1);
                map.put(arr[j],1);
                j++;   //往后移动
       
        }
        
        return res;
    }
}
滑动数组
发表于 2022-08-30 23:50:15 回复(0)
提交观点

问题信息

数组 哈希 双指针
难度：
112条回答 23508浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长无重复子数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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