给定一个长度为n的数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。
子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
数据范围:,
[2,3,4,5]
4
[2,3,4,5]是最长子数组
[2,2,3,4,3]
3
[2,3,4]是最长子数组
[9]
1
[1,2,3,1,2,3,2,2]
3
最长子数组为[1,2,3]
[2,2,3,4,8,99,3]
5
最长子数组为[2,3,4,8,99]
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; }
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; }
/** * * @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; }只用双指针,不用到哈希
/** * * @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 }