题解 | #最长无重复子数组#

最长无重复子数组

http://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4

题解一:暴力+hash表
主要思路:
①从1遍历到n,选取子数组的起点start
②第二重循环,从start下一个数字开始,选择子数组的结束位置end;
③直到end位置出现重复,记录最长的长度,跳转至步骤①,直到遍历完所有子数组的起点
图示:
图片说明

复杂度分析:
时间复杂度:,双重循环分别找子数组的头部和尾部
空间复杂度:,最差情况下,整个数组都是不重复的。

实现如下:

class Solution {
public:
    /**
     *
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        int res=0;
        for(int i=0;i<arr.size();++i){//遍历选取子数组的起点
            unordered_set<int> se;
            se.insert(arr[i]);
            for(int j=i+1;j<arr.size();++j){//遍历找到子数组的尾部
                if(se.count(arr[j])){//已经出现重复了,结束本次循环
                    break;
                }else{//本数字没有出现重复
                    se.insert(arr[j]);
                }
            }
            res=max(res,(int)se.size());//判断该子数组是否为最长无重复子数组
        }
        return res;
    }
};

题解二:双指针+hash表
主要思路:
①两个指针start,end,指向数组开始的位置
②移动start指针,并将指向的数字与hash表中数字进行比较,不同则加入hash表,继续②操作
③当start指针指向的数字在hash表中出现重复时,移动end指针,并删除指向的数字,直到hash表中没有与start指向的数字重复时,跳转至②
④直到start遍历完数组。
⑤在每一次将start指向的数字加入hash时,统计hash表中的大小,最大的size就是本题目答案res。
图示:
图片说明
复杂度分析:
时间复杂度:,左右指针都只会遍历一次数组
空间复杂度:,最差情况下,整个数组中的数字都是不重复的。

实现如下:

class Solution {
public:
    /**
     *
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        unordered_set<int> se;//存不重复的数字
        int i = 0, j = 0,res=0;
        while (i < arr.size()) {
            while (se.count(arr[i])) {//出现重复的数字,将hash表中这个值删除,删除到没有重复数字
                se.erase(arr[j++]);
            }
            se.insert(arr[i++]);//会将唯一的一个也删除,重新加入hash表中
            res = max(res, i - j);//统计此时的最大长度
        }
        return res;//返回结果
    }
};
牛客网编程题题解 文章被收录于专栏

本专栏记录在牛客网上AC的每一题,写下题解。 未来2年完成2000编程题的题解。 2021.12.29更新,最进准备毕设,断更了,会尽快做完毕设,继续做这一件事情

全部评论

相关推荐

头像
11-21 11:39
四川大学 Java
是红鸢啊:忘了还没结束,还有字节的5k 违约金
点赞 评论 收藏
分享
10-05 11:11
海南大学 Java
投票
理想江南137:感觉挺真诚的 感觉可以试一试
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务