LeetCode算法题:(3)求无重复字符的 最长子串 的长度（c语言）

本文主要是介绍LeetCode算法题:(3)求无重复字符的 最长子串 的长度（c语言），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

问题

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

示例

输入：abcabcbb

输出：3

解释：其无重复字符的最长子串为“abc”，长度为3

 题解

• 这里主要介绍滑动窗口解法，并先以最常见的暴力解法与其对比。

一、暴力解法

• 暴力解法的方式很直接，其思想是利用两层循环，第一层循环对字符串进行遍历，第二层循环对每一个遍历到的字符往后检索，得到无重复字符最长子串，并记录其长度，最后返回其最长子串的长度。

例：（abcbd）

1. (a)bcbd:最长子串为(abc)bd,长度为3
2. a(b)cbd:最长子串为a(bc)bd,长度为2
3. ab(c)bd:最长子串为ab(cbd),长度为3
4. abc(b)d:最长子串为abc(bd),长度为2
5. abcb(d):最长子串为abcb(d),长度为1

• 最后得到最长子串长度为3(这里主要介绍滑块窗口，故无代码片段)

二、滑块窗口

基本思想：滑动窗口可分为两个部分，一个是窗口的移动收缩，一个是重复字符的判断。

• 滑动窗口：针对存储字符串的数组，我们可以对数组进行遍历，同时对标记序号来记录其位置，然后用两个变量来记录窗口两边的位置（相当于两个指针），在遍历开始后，‘左指针’不动，‘右指针’往右移动，并同时判断两指针所限定的窗口中的子串是否有重复字符，如果有，则将‘左指针’移动到左重复字符之后的字符上，在这个过程中记录最大的子串长度，直到遍历结束。
• 标记序号：标记序号的实现是创建一个长度为128的数组，并把值都初始化为0，根据键盘所有可输入的字符的ascll码的值与数组序号一一对应，例如a：97、b：98、2:50，如此一来，相当于把所有可输入字符都存储在这个数组中，当我们对原数组遍历时，每遇到一个字符，便可以为其在此数组中标记一个序号。
• 重复判断：当我们的‘右指针’往右移动，每遇到一个字符，便判断其序号是否大于或等于‘左指针’的的序号，如果成立，便是遇到了重复字符 。 

注：初始化

流程图：

 代码实现：

int lengthOfLongestSubstring(char * s){
    int a[128]={0};
    int max=0,len=0,i=0,j=0;
    while(s[j]){
        if(a[s[j]]>i){
            i=a[s[j]];
        }
        a[s[j]]=j+1;
        len=j-i+1;
        max=max>len?max:len;
        j++;
    }
    return max;
}

这篇关于LeetCode算法题:(3)求无重复字符的 最长子串 的长度（c语言）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！