最长无重复子数组

﹏ヽ暗。殇╰゛Y 2023-10-01 09:39 1阅读 0赞

**题目要求：**![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

**分析：**

>  *  **主要还是借助于顺序表的特性，可随时添加新的元素，也可以清空自己已经存放的元素的特性**
>  *  **两层循环遍历，一层控制遍历的起始位置，一层控制循环的从起始位置开始的整个数组，更新max，更新count，和横向扫描相类似**
>  *  **具体详细操作，见代码注释**

import java.util.*;
    
    public class Solution {
        /**
         * 
         * @param arr int整型一维数组 the array
         * @return int整型
         */
        public int maxLength (int[] arr) {
            // write code here
            //我们的主要思路就是利用顺序表的动态数组，随时可添加，可删除的特性
            int max = 0;
            int count = 0;
            List<Integer> list = new ArrayList<>();
            int left = 0;
            /*
            1.两层循环，while循环的作用是从每一个位置开始确定起始遍历位置
            2.for循环，是从每一个给定的起始位置开始遍历，直到找到，最大max
            */
            while(left < arr.length){
                for(int i = left;i < arr.length;i++){
                    if(list.contains(arr[i])){
                        //更新max，确定这个子数组是不是当前最大的
                        max = list.size() > max ? list.size() : max ;
                        //既然已经确定了是从这个位置重复了，就清空list，为下一次遍历提供条件
                        list.clear();
                        count++;
                        /*
                        1.这里循环要跳出？那后面的元素呢？
                        2.因为外层循环while一定是要把数组每一个元素当做起始位置遍历一次的
                          所以，这个元素也会被当做起始位置开始遍历一次，在这里遍历得话会造成
                          重复计算
                        */
                        break;
                    }else{
                        //如果没有，加入这个元素
                        list.add(arr[i]);
                    }
                }
                //一层循环结束，清空list，继续为下一次循环提供条件
                list.clear();
                //更新起始位置
                left++;
            }
            //如果count == 0，且循环结束说明这个数组本身就是一个最大的子数组，返回即可
            if(count == 0){
                return arr.length;
            }
            return max;
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1424554643604ae2b79974271e0f2166.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16