首页 > 试题广场 >

最长无重复子数组

[编程题]最长无重复子数组

热度指数：329303 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

数据范围： $0\le arr.length \le 10^5$ ， $0 < arr[i] \le 10^5$

示例1

输入

[2,3,4,5]

输出

说明

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

示例2

输入

[2,2,3,4,3]

输出

说明

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

示例3

输入

[9]

输出

示例4

输入

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

输出

说明

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

示例5

输入

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

输出

说明

最长子数组为[2,3,4,8,99]

算法知识视频讲解

Java

Leeston520

最优解，滑动窗口+双指针：

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号

新建一个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号

记录以下自己逻辑漏洞的代码，代码逻辑为滑动窗口最大化，用一个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

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

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号

//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

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

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

滑动窗口

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)

Java

yxjing

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        ArrayList<Integer> list=new ArrayList<Integer>();
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int left=0,right=0;right<=arr.length-1;right++){
            map.put(arr[right],map.getOrDefault(arr[right],0)+1);
            if(map.get(arr[right])>1){
                list.add(right-1-left+1);
                while(left<right&&map.get(arr[right])>1){
                    map.put(arr[left],map.get(arr[left])-1);
                    left++;
                }
            }
        }
        Collections.sort(list);
        return list.isEmpty()?arr.length:list.get(list.size()-1);
    }
}

发表于 2022-08-17 21:34:34 回复(0)

Java

lizi-hust

import java.util.*;
public class Solution {
    public int maxLength (int[] arr) {
        if(arr==null || arr.length==0) return 0;
        int n = arr.length;
        HashSet<Integer> set = new HashSet<>();
        
        int res = 0, left = 0, right = 0;
        while(right < n){
            int num = arr[right];
            if(!set.contains(num)) {
                set.add(num);
                right++;
                res = Math.max(res, right - left);
            }else{
                while(arr[left] != num){
                    set.remove(arr[left++]);
                }
                set.remove(arr[left++]);
            }
        }
        return res;
    }
}

发表于 2022-08-07 16:18:36 回复(0)

Java

wslok

public int maxLength(int[] arr) {
    // write code here
    //给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
    //子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
    // 滑动窗口
    // 跟********第3题一样的解法
    // https://********.cn/problems/longest-substring-without-repeating-characters/
    if (arr == null || arr.length == 0) {
        return 0;
    }
    Set<Integer> set = new HashSet<>();
    // 双指针
    int left = 0, right = 0;
    // 用来存储最长子数组长度
    int len = 0;
    while (right < arr.length) {
        // 数组右边数字
        int c = arr[right];
        while (set.contains(c) && left < right) {
            set.remove(arr[left]);
            left++;
        }
        set.add(c);
        right++;
        len = Math.max(len, right - left);
    }
    return len;
}

编辑于 2022-07-19 16:47:31 回复(0)

Java