【力扣LeetCode】3 无重复字符的最长子串

题目描述（难度中）

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

示例 1:

输入: “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”

输出: 1

解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”

输出: 3

解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

链接

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

思路

用一前一后两个指针移动，前面的指针移动一下，判断移动后加入的字符是否与子串中字符有重复，如果没有，更新最大值，如果有，则移动后面的指针至指向与新加入字符相同的字符处，然后更新最大值（其实肯定不会更大）。

1、判断字符是否在子串中，我采用的方案1做法为，用一个set集合快速判定是否该字符在子串中。判定速度较快，但是插入和删除就会比较影响速度。

2、方案2，可使用

C++ string

提供的

indexOf

函数快速找到子串中是否含有某一字符，并且可返回相应的下标，查找速度慢一些，但是整体上速度快一些。

indexOf

用法如下，详见：https://www.cnblogs.com/zhangshi/p/6502987.html

思路如下：

代码

方案1：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    	if(s.length() == 0){
    		return 0;
    	}
        set<char> cset;
		int ans = 1;
        int i = 0; 
        int j = 1;
        cset.insert(s[0]);
        while(j < s.length()){
        	if(cset.find(s[j]) == cset.end()){
        		cset.insert(s[j]);
        		j++;
        		if(ans < j-i){
        			ans = j-i;
        		}
        	}
        	else{
        		while(s[i]!=s[j]){
        			cset.erase(cset.find(s[i]));
        			i++;
        		}
        		i++;
        		j++;
        		if(ans < j-i){
        			ans = j-i;
        		}
        	}
        }
        return ans;
    }
};
           

方案2：

class Solution {
	public int lengthOfLongestSubstring(String s) {
		int i = 0;
		int flag = 0;
		int length = 0;
		int result = 0;
		while (i < s.length()) {
			int pos = s.indexOf(s.charAt(i),flag);
			if (pos < i) {
				if (length > result) {
					result = length;
				}
				if (result >= s.length() - pos - 1) {
					return result;
				}
				length = i - pos - 1;
				flag = pos + 1;
			}
			length++;
			i++;
		}
		return length;
	}
}