題目
給定一個(gè)字符串湿镀，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度舵盈。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。
示例 2:輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "b"斩祭，所以其長(zhǎng)度為 1弟翘。
示例 3:輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "wke"烘跺，所以其長(zhǎng)度為 3闹击。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度凹联，"pwke" 是一個(gè)子序列沐兰，不是子串。
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
解題
方法一：滑動(dòng)窗口（逐個(gè)）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//char[] chars = new char[256];
int chars[256]={0}; //ASCII表有127個(gè)字符 還有個(gè)128的副表 因此申請(qǐng)256個(gè)空間 用于計(jì)數(shù)
int begin = 0;
int res = 0;
for(int i = 0;i<s.length();i++){
while(begin <= i && chars[s.at(i)] > 0){//處理當(dāng)前添加的字符重復(fù)的問題
//下面代碼是用于逐個(gè)往前滑動(dòng) 去重
chars[s.at(begin)]--;
begin++;
}
chars[s.at(i)]++;//每次不重復(fù)子串的長(zhǎng)度+1
res = max(res,i - begin + 1);//記錄不重復(fù)子串的最長(zhǎng)長(zhǎng)度
}
return res;
}
};
注意
取單個(gè)字符操作：
- C++為 string.at()
- JAVA為 string.charAt()
-
string也可以視為數(shù)組形式 直接取就可以 例如 s="abcd",s[2] = "c"蔽挠。
字符集
方法二
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> data;
int begin = 0, result = 0;
//i代表字串的起始位置住闯，j表示字串的結(jié)束位置
for (int j = 0; j < s.size(); j++) {
if (data.find(s[j]) != data.end()) {
begin = max(begin, data[s[j]]);//當(dāng)有字符重復(fù)時(shí)更新字串起始位置
}
result = max(result, j - begin + 1);//判斷當(dāng)前字串與歷史字串長(zhǎng)度的大小
data[s[j]] = j + 1;//記錄并更新這個(gè)字符最近出現(xiàn)的位置 此處相當(dāng)于存儲(chǔ)之前與之重復(fù)的元素的下一個(gè)位置
}
return result;
}
};
for (int j = 0; j < s.size(); j++) {
if (data.find(s[j]) != data.end()) {
begin = max(begin, data[s[j]]);//當(dāng)有字符重復(fù)時(shí)更新字串起始位置
}
result = max(result, j - begin + 1);//判斷當(dāng)前字串與歷史字串長(zhǎng)度的大小
data[s[j]] = j + 1;//記錄并更新這個(gè)字符最近出現(xiàn)的位置
}
不能寫為以下這種形式
for (int j = 0; j < s.size(); j++) {
if (data.find(s[j]) != data.end()) {
begin = max(begin, data[s[j]]);//當(dāng)有字符重復(fù)時(shí)更新字串起始位置
begin++;
}
result = max(result, j - begin + 1);//判斷當(dāng)前字串與歷史字串長(zhǎng)度的大小
data[s[j]] = j ;//記錄并更新這個(gè)字符最近出現(xiàn)的位置
}
這種形式的錯(cuò)誤在于，循環(huán)有時(shí)候會(huì)誤加澳淑，我們本意是取重復(fù)元素的下一個(gè)作為開始寞秃，但是map存儲(chǔ)了所有的元素，因此有時(shí)即使無效的重復(fù)也會(huì)進(jìn)入循環(huán)偶惠，使begin+1，減少了長(zhǎng)度朗涩。
上面例子就是忽孽，begin在第二個(gè)m處時(shí)，當(dāng)運(yùn)行到最后一個(gè)t谢床，由于之前map有保存key為t兄一，因此會(huì)進(jìn)入循環(huán)识腿，使begin++骂束，因此長(zhǎng)度變短，因此此時(shí)的操作屬于誤操作混驰。
所以直接用數(shù)據(jù)存儲(chǔ)下一個(gè)位置這種形式比較可靠昆汹。
