题解 | #最长无重复子数组#
最长无重复子数组
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更新,最进准备毕设,断更了,会尽快做完毕设,继续做这一件事情