首页 > 试题广场 >

找到字符串的最长无重复字符子串

[编程题]找到字符串的最长无重复字符子串
  • 热度指数：3587 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有字母都不相同)。

输入描述:
输入包含两行，第一行包含一个整数n，代表数组arr的长度,第二行包含n个整数，代表数组arr。


输出描述:
输出一个整数，代表arr的最长无重复字符的长度。
示例1

输入

4
2 3 4 5

输出

4
示例2

输入

5
2 2 3 4 3

输出

3

备注:
时间复杂度，额外空间复杂度。
算法知识视频讲解
添加回答
C
helloxuanbao头像 helloxuanbao 
#include <stdio.h>
#include <stdlib.h>

#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
#define MAX_VAL 1000001

int main(void) {
    int n, *arr, pre_idx[MAX_VAL];
    int tmp, pre_len = -1, ans = 0;
    scanf("%d", &n);
    arr = (int *) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    for (int i = 0; i < MAX_VAL; i++) {
        pre_idx[i] = -1;
    }
    for (int i = 0; i < n; i++) {
        tmp = i - pre_idx[arr[i]];
        if (i != 0 && arr[i] != arr[i - 1])
            tmp = MIN(tmp, pre_len + 1);
        ans = MAX(ans, tmp);
        pre_len = tmp;
        pre_idx[arr[i]] = i;
    }
    printf("%d\n", ans);
    free(arr);
    return 0;
}

发表于 2022-02-11 18:09:06 回复(0)
Java
pein531头像 pein531
双指针滑动窗口求解，刚开始两个指针都在0位置，如果元素一直不重复就扩张右边界，重复了就更新长度并收缩左边界，在这个遍历的过程中使用哈希表来进行判重。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        int left = 0, right = 0;
        HashSet<Integer> used = new HashSet<>();
        int maxLen = 0;
        while(right < n){
            if(!used.contains(arr[right])){
                used.add(arr[right]);       // 一直不重复就一直扩张右边界
                right++;
            }else{
                // 重复了就更新长度，收缩左边界，直到把第一次出现的重复元素排除掉
                maxLen = Math.max(maxLen, right - left);
                while(left < right && arr[left] != arr[right]){
                    used.remove(arr[left]);
                    left++;
                }
                left++;
                right++;
            }
        }
        maxLen = Math.max(maxLen, right - left);
        System.out.println(maxLen);
    }
}

发表于 2021-11-27 10:36:34 回复(0)
牛客79631828号头像 牛客79631828号 
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            max = Math.max(max, arr[i]);
        }
        System.out.println(getMaxSubLen(arr, max));
    }
    
    public static int getMaxSubLen(int[] arr, int max) {
        if (arr == null || arr.length == 0)
            return 0;
        //index表示遍历到的某个数，value表示这个字符最近一次出现的位置
        //map[arr[i]]表示之前的遍历中最近一次出现arr[i]的位置
        int[] map = new int[max+1];
        for (int i = 0; i < map.length; i++) {
            map[i] = -1;
        }
        //如果当前遍历到arr[i], 表示在必须以arr[i-1]字符结尾时，
        //最长无重复子串开始位置的前一个位置
        int pre = -1;
        int len = 0;
        int cur = 0;
        //假设arr[i]之前出现过的位置是a, 若a在pre左侧，则当前最长长度为i-pre;
        //若a在pre右侧，则当前最长长度为i-a
        for (int i = 0; i < arr.length; i++) {
            //既然要么-a，要么-pre，那就谁大谁当被减去的数吧
            pre = Math.max(pre, map[arr[i]]);
            cur = i-pre;
            len = Math.max(len, cur);
            map[arr[i]] = i;
        }
        return len;
    }
}

发表于 2021-08-02 01:04:20 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int k=0, l=0;
    unordered_map<int, int> mp;
    for(int i=0;i<n;i++){
        if(mp.find(a[i])==mp.end() || mp[a[i]]<k)
            l = max(l, i-k+1);
        else
            k = mp[a[i]];
        mp[a[i]] = i+1;
    }
    cout<<l<<endl;
    return 0;
}

发表于 2020-05-16 01:05:59 回复(0)
折纸201910211308379头像 折纸201910211308379
java 动态规划 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int[] dp = new int[n];
        dp[0] = 1;
        int res = 0;
        for(int i=1;i<n;i++){
            boolean sign = false;//false表示没找到与自己相等的元素；
            for(int p=1;p<=dp[i-1];p++){
                if(arr[i] == arr[i-p]){
                    sign = true;
                    dp[i] = p;
                    break;
                }
            }
            if(!sign) dp[i] = dp[i-1] + 1;
            res = res >= dp[i] ? res : dp[i];
        }
        System.out.println(res);
    }
}


发表于 2021-10-06 20:49:41 回复(0)
Java
眼睛想旅行121头像 眼睛想旅行121 
import java.io.*;

public class Main{
    public static int maxUnique(int[] str){
        if(str==null||str.equals("")){
            return 0;
        }
        int[] map=new int[256999];
        for(int i=0;i<256999;i++){
            map[i]=-1;
        }
        int len=0;
        int pre=-1;
        int cur=0;
        for(int i=0;i<str.length;i++){
            pre=Math.max(pre,map[str[i]]);
            cur=i-pre;
            len=Math.max(len,cur);
            map[str[i]]=i;
        }
        return len;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine().trim());
        int[] str = new int[n];
        String[] ops = br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            str[i] = Integer.parseInt(ops[i]);
        }
        System.out.print(maxUnique(str));
    }
}

发表于 2021-03-31 12:01:24 回复(0)
Python
职场小白3号头像 职场小白3号 

def solution(str,n):
    begin=0
    end=0
    l=[[]for i in range(n)]
    j=0
    maxs=0
    for end in range(n):
        if str[end] not in l[j]:
            l[j]=l[j].append(str[end])
           
            end+=1
            maxs=max(maxs,end-begin)
        else:
            begin=l[j].index(str[end])+1
            j+=1
            l[j]+=l[j-1][begin:]
            l[j]=l[j].append(end)
            
            end+=1
            maxs=max(maxs,end-begin)
    return maxs


发表于 2020-09-20 16:29:41 回复(0)
深色浅色56头像 深色浅色56 
n = int(input())
a = list(input().split())
start = 0
max_len = 1
dic = {}
for i in range(len(a)):
    if a[i] in dic and dic[a[i]] >= start:
        start = dic[a[i]] + 1
    dic[a[i]] = i
    max_len = max(max_len, i-start+1)
print(max_len)

发表于 2020-08-25 15:38:41 回复(0)
嘉定小汽车头像 嘉定小汽车 
//代码没通过牛客，在VS上试了试小范围的n，功能测试可以的。
//不知道出现什么情况，也是溢出了吗？
//大佬路过帮忙指点下
#include<iostream>
#include<string>
#include<unordered_set>
using namespace std;
int main()
{
	long int n,num;
	unordered_set<long int>myset;
	scanf("%ld", &n);
	for (long int i = 0;i < n;++i)
	{
		scanf("%ld", &num);
		myset.insert(num);
	}
	cout << myset.size() << endl;
}

发表于 2020-07-22 15:57:40 回复(2)
爱看电影的里根是单身头像 爱看电影的里根是单身
子串和子序列区别：子串必须连续，子序列可以断开
发表于 2020-07-10 01:02:28 回复(0)
镜镜詅痴头像 镜镜詅痴
有大佬可以帮我解释一下哪里段溢出(没有递归啊，leetcode可以AC双百) 
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int lengthOfLongestSubstring(vector<int>& s) {
    if(s.size()<1){
        return 0;
    }
    int Hashmap[10]; // map用来记录当前出现的数字前一次出现的索引
    for(int i=0;i<10;i++){
        Hashmap[i] = -1;
    }
    int start = 0; // 表示当前最长的无重复字符串的起始位置
    int res = 1;
    Hashmap[s[0]] = 0;
    for(int i=1;i<s.size();i++){
        int indx = Hashmap[s[i]]; // 查看s[i]在Hashmap中的值
        if(indx>=start){
            // 如果indx>start说明当前的字符s[i]已经在当前的最长无重复字符串中出现过了
            res = max(res,(i-start));
            start = indx+1; // 将最长无重复字符串的起始位置调成indx的下一位
        }
        // 更新map
        Hashmap[s[i]] = i;
    }
    // 遍历完了以后再更新一次res
    int cur = s.size()-start;
    res = max(res,cur);
    return res;
}




int main(){
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<lengthOfLongestSubstring(arr);
}


发表于 2020-05-24 14:00:24 回复(1)
junnerm头像 junnerm 
#include<iostream>
(720)#include<algorithm>
#include<vector>
using namespace std;
int main(void) {
    int n = 0;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    //因为字符无重复最小为1，初始化为1
    vector<int >dp(n, 1);    
    int max = 0;
    for (int i = 1; i < n; i++) {//首个字符肯定无重复，不进行处理
        if (arr[i] == arr[i - 1])//如果重复，跳过
            continue;
        dp[i]++;                //不相同，则加上自身
        int j = i-1;
        //循环条件为辅助vector中的不相同的值的范围，判定当前字符与范围中的字符是否存在重复
        for (int k = dp[i - 1]; k > 1; k--) { 
            if (dp[j--] == 1)    //当其等于1，则说明dp[j]前一个字符与dp[j]字符相同
                break;
            if (arr[i] != arr[j])
                dp[i]++;
            else {                //如果当前字符与范围中的字符存在重复，则跳出
                break;
            }
        }
        if (dp[i] > max)
            max = dp[i];
    }
    cout << max << endl;
    return 0;
}

发表于 2020-04-19 18:16:16 回复(0)
C/C++
Janie_97头像 Janie_97
思路就是运用一个空间为max(arr[n])的hash表将查询时间复杂度降为O(1)，则整体时间复杂度为O(n)。
思路很明确，但是提交了很多次都没通过，最后发现居然是因为面试一开始太紧张，hash表定义出了问题，定义为int hash_table[1<<7]（面试时脑子短路了，以为是10^7），也就是2^7，远远不够10^6，后来改成定义hash_table[1000009]就通过了，真是细节决定成败。 
#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }
    int pre = 0, len = 0;
    int hash_table[1000009] = {0};
    for (int i = 0; i < n; i++){
        if (hash_table[arr[i]] == 0 || hash_table[arr[i]] < pre){
             len = max(len, i - pre + 1);
        }else{
            pre = hash_table[arr[i]];
        }
        hash_table[arr[i]] = i + 1;
    }
    cout << len;
    return 0;
}

编辑于 2020-04-02 20:24:53 回复(0)
小小小小飞侠头像 小小小小飞侠
#include<iostream>
using namespace std;
int A[100001];
int main() {
    int n; int length = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    int start = 0; int i = 1;
    while (i < n) {
        int temp = 1;
        for (int j = start; j < i; j++) {
            if (A[j] == A[i]) {
                start = j + 1;
            }
            else {
                temp++;
            }
            if (temp > length)length = temp;
        }
        i++;
    }
    cout << length;
    return 0;
}
发表于 2020-02-12 10:59:13 回复(0)
Python
奔跑bin头像 奔跑bin
n = int(input())
arr = input().split()

   
start = 0
ans = 1
last_pos = {}


for i in range(n):  
    if arr[i] in last_pos.keys():
        ans = max(ans,i - start)
        start = i 
    last_pos[arr[i]] = i


ans = max(ans, n - start)
   
print(ans)

我这样写有什么错啊 ？？？
发表于 2020-02-05 20:04:43 回复(1)
Learn2Learn头像 Learn2Learn 
n=int(input())
arr=list(input().split())
last_pos={}
res=1
start=0# 记录起始点
for i in range(n):
    if arr[i] in last_pos and start<=last_pos[arr[i]]:
        start=last_pos[arr[i]]+1#如果出现重复字符更新起始点位置
    last_pos[arr[i]]=i#更新保存的位置
    res=max(res,i-start+1)#更新非重复字符长度
print(res)      

发表于 2019-09-09 14:51:34 回复(0)
PopcornZQ头像 PopcornZQ 
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>

using namespace std;
int main()
{
	int n,left=0,right=0,result=0;//窗口左边界、窗口右边界
	unordered_set<int>jilu;
	cin >> n;
	vector<int>re(n);
	for (int i = 0; i < n; i++)
		cin >> re[i];
	while (left < n && right < n)
	{
		if (!jilu.count(re[right]))//不存在
		{
			jilu.insert( re[right++] );
			result = max(result, right - left);
		}
		else
			jilu.erase(re[left++]);
	}
	cout << result;
}

发表于 2019-09-08 12:47:12 回复(0)
随缘秋招头像 随缘秋招 
import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] nums = new int[n];
            for (Integer i = 0; i < n ; i++) {
                nums[i] = sc.nextInt();
            }
            int res = maxUnique(nums,n);
            System.out.println(res);
        }
    }

    private static int maxUnique(int[] nums, int n) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < n ; i++) {
            int temp = nums[i];
            if(map.get(temp) == null)
                map.put(temp,-1);
        }
        int len = 0;
        int pre = -1;
        int cur = 0;
        for (int i = 0; i < n ; i++) {
            int temp = nums[i];
            pre = Math.max(pre,map.get(temp));
            cur = i - pre;
            len = Math.max(len,cur);
            map.put(temp,i);
        }
        return len;
    }
}

发表于 2019-08-15 09:19:29 回复(0)
提交观点

问题信息

字符串 模拟
上传者：小小
难度：
18条回答 8866浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号