首页 > 试题广场 >

最长无重复子数组

[编程题]最长无重复子数组
  • 热度指数:326366 时间限制: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]     
/**
 *
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return int整型
 */
int maxLength(int* arr, int arrLen ) {
    // write code here
    if(0 == arrLen) return 0;
    else if(1 == arrLen) return 1;
    int head = 0, tail = 0;
    int width = 1, ret = 1;
   
    for(tail = 0; tail < arrLen; tail++)
    {
        if(tail == head) continue;
        int i = head,eq = 0;
        for( i = head; i < tail; i++)
        {
            if(arr[i] == arr[tail])
            {
                eq = 1;
                break;
            }
        }
        if(eq) head = i + 1;
        width = tail - head + 1;
        if(width > ret) ret = width;
       
      
    }
    return ret;
                           
}
发表于 2021-08-28 10:38:06 回复(0)
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)
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;

发表于 2021-04-02 17:20:56 回复(1)
//之前创建了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)
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)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @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)
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)
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)
    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)
利用动态规划
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)

发表于 2021-09-01 14:16:54 回复(0)
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
暴力法
发表于 2021-09-01 10:37:36 回复(0)
/**
 *
 * @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)
    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);
    }

发表于 2021-08-07 14:56:36 回复(0)
#
# 
# @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
    
    
    
    
    
    
    
    

发表于 2021-08-07 09:55:19 回复(0)
为啥我这个有一个案例不通过呢
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;
    }
}


发表于 2021-08-04 22:16:02 回复(2)
思路:分配一个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)
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)
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)
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)