【力扣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;
	}
}