当前位置：首页 > article >正文

后端开发刷题 | 最长无重复子数组

article 2024/9/23 21:49:09

描述

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

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

数据范围：0≤arr.length≤105，0<arr[i]≤105

示例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]

思路分析：

方法1：

该题可以使用队列来实现，因为队列先进先出，后进后出的特性，在遇到重复元素可以通过queue.poll()的方法把队头元素出队，使队列里面没有重复元素。

并且每添加一个元素，就比较最大值个数来更新res。

代码：

import java.util.*;


public class Solution {
    /**
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        Queue<Integer> queue=new LinkedList<>();
        int res=0;
        for(int c:arr){
            while(queue.contains(c)){
                //如果有重复的元素，则让队头出队，一直到队列里面没有重复元素
                queue.poll();
            }
            //添加元素到队尾
            queue.add(c);
            res=Math.max(res,queue.size());
        }
        return res;
      
    }
}

思路分析：

方法2：

可以使用“滑动窗口”技术，是一种常用于解决数组/字符串中满足特定条件的子数组/子串问题的技术。在这个问题中，通过维护一个窗口（即左右指针之间的部分），并使用哈希集合来快速检查元素是否重复，我们能够高效地找到最长无重复元素子数组的长度。

步骤：

初始化变量：
- left 和 right 是两个整型指针，分别表示当前考虑的子数组的左右边界。初始时，它们都指向数组的第一个元素（即索引 0）。
- max 用于记录迄今为止找到的最长无重复元素子数组的长度。初始值为 0。
- set 是一个 HashSet，用于存储当前考虑的子数组中的元素，以便快速检查元素是否重复。
遍历数组：
- 使用一个 while 循环遍历数组 arr，条件是 right 指针小于数组的长度。这意味着只要 right 指针没有超出数组的范围，循环就会继续。
处理重复元素：
- 在每次循环中，首先检查 set 是否已经包含了 arr[right]。这是通过调用 set.contains(arr[right]) 来实现的。
- 如果 set 包含 arr[right]，说明当前考虑的子数组中出现了重复元素。此时，需要从子数组中移除左边界的元素（即 arr[left]），直到不再重复为止。这是通过循环调用 set.remove(arr[left++]) 来实现的，同时 left 指针向右移动。
添加元素并更新最长长度：
- 如果 set 不包含 arr[right]，说明当前元素可以添加到子数组中。此时，将 arr[right] 添加到 set 中，并将 right 指针向右移动。
- 然后，检查并更新 max 的值，以确保它始终表示当前找到的最长无重复元素子数组的长度。这是通过调用 max = Math.max(max, set.size()) 来实现的。注意，这里我们直接使用了 set.size() 来获取当前无重复元素子数组的长度。
返回结果：
- 当 right 指针超出数组范围时，循环结束。此时，max 变量中存储的就是最长无重复元素子数组的长度。方法返回这个值。

代码：

import java.util.*;


public class Solution {
    /**
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
       int left=0,right=0;
       Set<Integer> set=new HashSet<>();
       int max=0;
       while(right<arr.length){
        if(set.contains(arr[right])){
            set.remove(arr[left++]);
        }else{
            set.add(arr[right++]);
            max=Math.max(max,set.size());
        }
       }
       return max;
      
    }
}

查看全文

http://www.kler.cn/news/316615.html