给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
数据范围：
，
[编程题]最长无重复子数组
- 热度指数：363257 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
示例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]
int maxLength(int* arr, int arrLen ) {
if (arrLen == 0) return 0;
int max = 0;
int left = 0;
for (int right=0; right<arrLen; ++right)
{
if (right - left > 0)
{
//遍历right左边的元素和right比较，若相同则移动left的位置
for (int i=left; i<right; ++i)
{
if (arr[right] == arr[i]) left = i + 1;
}
max = ((right - left) > max) ? right - left : max;
}
}
return max+1;
}
发表于 2024-05-28 19:51:22
回复(0)
//具体思路是创建一个数组ret来存储待会需要用到。我的想法很简单就是暴力算法，若arr长度为0或者1直接输出；若不是，则从arr数组下标为0开始循环，例如从下标为0开始找最长的无重复，直到重复，则保存好当前的数组长度。然后继续从下标为2开始循环直到最后一个下标。期间怎么判断这个数值重复出现，即第2次出现呢？用一开始定义好的ret数组来，每次使用都清0，开始简单判断当前的数组下标和下一个下标的数组是否相同，如果不同则ret的下标为那个arr数组的值=ret的下标为那个arr数组的值+1.当大于1时立刻终止内循环，外循环从下一个开始。
int maxLength(int* arr, int arrLen ) {
// write code here
int mval=0,maxval=0,ret[100000];
for(int i=0;i<arrLen;i++){
int val=0;
for(int k=0;k<arrLen;k++){
ret[k]=0;
}
if(arrLen==0||arrLen==1){
return arrLen;
}
for(int j=i;j<arrLen;j++){
if(arr[j]!=arr[j+1]){
ret[arr[j]]=ret[arr[j]]+1;
if(ret[arr[j]]>1){
break;
}
val=val+1;
}
if(arr[j]==arr[j+1]){
break;
}
}
maxval=fmax(maxval,val);
}
return maxval;
}
发表于 2024-05-24 23:36:55
回复(1)
int JudgeArr(int* arr, int arrLen, int s) {
int i;
for(i=0;i<arrLen;i++) {
if(arr[i]==s)
return i+1;
}
return 0;
}
int maxLength(int* arr, int arrLen ) {
// write code here
int *start,*end,MaxLengthRecord=0,MaxLength=1;
if(arrLen==0)
return 0;
start = arr;
end = arr;
MaxLengthRecord++;
while(end!=arr+arrLen-1) {
int RepectSLOC = JudgeArr(start,MaxLengthRecord,*(end+1));
if(RepectSLOC) {
start+=RepectSLOC;
MaxLengthRecord-=RepectSLOC;
}
else {
MaxLengthRecord++;
end++;
}
if(MaxLength<MaxLengthRecord)
MaxLength=MaxLengthRecord;
}
return MaxLength;
}
编辑于 2024-03-13 15:26:09
回复(0)
int maxLength(int* arr, int arrLen ) {
if(arrLen == 0 || arrLen == 1)
{
return arrLen;
}
int iArray[100000] ={0};
int iCounter = 0;
int length = 0;
int max = 0;
int left = 0;
memset(iArray,0,sizeof(iArray));
for(int right = 0; right < arrLen; right++)
{
iArray[arr[right]]++;
while(iArray[arr[right]] > 1)
{
/*z注意哦*/
iArray[arr[left]]--;
left = left+1;
}
if(right - left+1 > max)
{
max =right - left+1;
}
}
return max;
}
发表于 2023-03-12 20:40:39
回复(0)
int maxLength(int* arr, int arrLen ) {
if(arrLen == 0 || arrLen ==1)
return arrLen;
int hm[102400] = {0};//定义一个数组用作hashmap
int len = 0;
for(int left=0, right=0; right < arrLen; right++)
{
while(hm[arr[right]] != 0 )//如果遇到重复，滑动窗口
{
hm[arr[left]]=0;
left++;
}
hm[arr[right]]=1;
if(right-left+1 > len)
len = right-left+1;
}
return len;
}
发表于 2022-08-04 02:26:57
回复(1)
int maxLength(int* arr, int arrLen ) {
// write code here
if(arrLen<=1)
{
return arrLen;
}
int iRet=0;//返回结果
int temp=0;//临时大小
int l=0; //左边下标
int r=1; //右边下标
int j=0;
for(r=1;r<arrLen;r++)
{
//第r个值与l~r-1之间的比较
for(j=l;j<r;j++)
{
if(arr[j]==arr[r]) //r与j相等
{
l=j+1; //将做下标迁移至下一位
}
}
if(j==r)//中间没有重复
{
temp=r-l+1;
if(iRet<temp)//当前最大值小于新的最大值
{
iRet=temp;
}
}
}
return iRet;
}
// write code here
if(arrLen<=1)
{
return arrLen;
}
int iRet=0;//返回结果
int temp=0;//临时大小
int l=0; //左边下标
int r=1; //右边下标
int j=0;
for(r=1;r<arrLen;r++)
{
//第r个值与l~r-1之间的比较
for(j=l;j<r;j++)
{
if(arr[j]==arr[r]) //r与j相等
{
l=j+1; //将做下标迁移至下一位
}
}
if(j==r)//中间没有重复
{
temp=r-l+1;
if(iRet<temp)//当前最大值小于新的最大值
{
iRet=temp;
}
}
}
return iRet;
}
发表于 2022-02-16 16:12:10
回复(0)
/**
*
* @param arr int整型一维数组 the array
* @param arrLen int arr数组长度
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int maxLength(int* arr, int arrLen ) {
int str=0,dest=1;
int max=0;
if(arrLen>1)//如果len为1，while循环进不去，直接返回max【此时max==0】不合题意
{
while(dest<arrLen)
{
for(int i=str;i<dest;i++)
{
if(arr[i]==arr[dest])
{
//如果dest和其前面所有元素比较结果是：有相等的，就让str=i+1
//不能str=dest【要考虑到[1,2,1,3]这种情况，如果是str=dest那么直接就剩1,3了】
str=i+1;
break;
}
}
max=max>(dest-str+1)?max:(dest-str+1);//记录最大长度
dest++;
}
return max;
}
return arrLen;
}
只用双指针，不用到哈希
发表于 2021-12-05 22:34:29
回复(1)
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int maxLength(int* arr, int arrLen ) {
// write code here
int x=0,max=0;
for(int right=0;right<arrLen;right++)
{
int left=right-1;
while(left>=x && arr[right]!=arr[left]){
left--;
}
if(left==x-1 && right-x+1>max) max=right-x+1;
else x=left+1;
}
return max;
}
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int maxLength(int* arr, int arrLen ) {
// write code here
int x=0,max=0;
for(int right=0;right<arrLen;right++)
{
int left=right-1;
while(left>=x && arr[right]!=arr[left]){
left--;
}
if(left==x-1 && right-x+1>max) max=right-x+1;
else x=left+1;
}
return max;
}
发表于 2021-12-03 17:38:19
回复(0)
/**
*
* @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;
}
*
* @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)
/**
*
* @param arr int整型一维数组 the array
* @param arrLen int arr数组长度
* @return int整型
*/
int maxLength(int* arr, int arrLen ) {
int i,j;
int p=0;
for(i=0;i<arrLen-1;i++)
{
for(j= i+1;j<arrLen;j++)
{
if(arr[i] ==arr[j] && arr[i] !=0)
{
arr[j] =0;
p++;
}
}
}
p = p=arrLen;
return p;
// write code here
}
发表于 2021-08-09 20:16:44
回复(0)
#include<stdio.h>
void maxLength(int a[], int arrLen )
{
int i,j;
int count=0;//用来返回count值
printf("该无重复子数组为：");
for(j=0;j<arrLen;j++)
{
if(a[j+1]==a[j])
{
continue;
}else
{
for(i=0;i<j;i++)
{
if(a[j]==a[i])
{
break;
}else
{
continue;
}
}
if(i==j||i==j-1)
{
printf("%d ",a[j]);
count++;
}
}
}
printf("\n");
printf("最长无重复子数组元素个数为：%d\n",count);
return;
}
int main()
{
int m,i;
printf("输入数组元素个数：");
scanf("%d",&m);
int a[m];
printf("输入数组各元素：");
for(i=0;i<m;i++)
{
scanf("%d",&a[i]);
}
maxLength(a,m);
void maxLength(int a[], int arrLen )
{
int i,j;
int count=0;//用来返回count值
printf("该无重复子数组为：");
for(j=0;j<arrLen;j++)
{
if(a[j+1]==a[j])
{
continue;
}else
{
for(i=0;i<j;i++)
{
if(a[j]==a[i])
{
break;
}else
{
continue;
}
}
if(i==j||i==j-1)
{
printf("%d ",a[j]);
count++;
}
}
}
printf("\n");
printf("最长无重复子数组元素个数为：%d\n",count);
return;
}
int main()
{
int m,i;
printf("输入数组元素个数：");
scanf("%d",&m);
int a[m];
printf("输入数组各元素：");
for(i=0;i<m;i++)
{
scanf("%d",&a[i]);
}
maxLength(a,m);
}
//这在线编译器这么死板，在这不成功在Red Panda Dev-C++能行，虽然我还是个小白
发表于 2021-07-17 16:31:12
回复(0)
问题信息
难度：
19条回答
1970收藏
24013浏览
通过挑战的用户
查看代码-
2023-02-27 15:07:28
-
2022-11-25 10:16:54 -
2022-10-22 15:00:21 -
2022-10-16 16:06:19
-
2022-10-05 22:02:32
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
