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

[编程题]找到字符串的最长无重复字符子串

热度指数：3587 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有字母都不相同)。

输入描述:

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

输出描述:

输出一个整数，代表arr的最长无重复字符的长度。

示例1

输入

4
2 3 4 5

输出

示例2

输入

5
2 2 3 4 3

输出

备注:

时间复杂度，额外空间复杂度。

算法知识视频讲解

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)