leetcode 之无重复字符的最长子串

前言

今天leecode上看到一个题目，分享给大家，我也给出了解答，大家可以参考下，这种解法还可以进行优化，比如采用哈希算法代替比较。

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

答案解答

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


int lengthOfLongestSubstring(char *s) {
    int len = strlen(s);
    char *t = s, *p_start = s, *temp;
    int max_len = 0;
    int t_len = 0;
    char c;
    while (t < (s + len)) {
        if (t == s) {
            ++t;
            ++t_len;
            continue;
        }

        c = *t;
        temp = t;
        while (--temp >= p_start && *temp != c);
        if (temp >= p_start) {
            p_start = temp + 1;
            if (t_len > max_len) {
                max_len = t_len;
            }
            t_len = t - p_start+1;
            t++;
        } else {
            ++t_len;
            ++t;
        }
    }
    if (t_len > max_len) {
        max_len = t_len;
    }
    return max_len;
}

int main() {
    char *input = "hello";
    printf("%d\n", lengthOfLongestSubstring(input));
    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接