[Leetcode] 3 - Longest Substring Without Repeating Characters
1100 ワード
原題リンク:https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
2つのindex,left,right,すなわち通常1つのウィンドウを維持する方法である.rightが1進むたびに、現在のrightが指すcharが前に現れなければ、前進を続けます.現在rightが指すcharが現れた場合(このcharをcと呼ぶと仮定)、leftをcが現れたindex+1の位置に移動する.その後rightを増やし続けます.
*注意文字は英字のみではありません
2つのindex,left,right,すなわち通常1つのウィンドウを維持する方法である.rightが1進むたびに、現在のrightが指すcharが前に現れなければ、前進を続けます.現在rightが指すcharが現れた場合(このcharをcと呼ぶと仮定)、leftをcが現れたindex+1の位置に移動する.その後rightを増やし続けます.
*注意文字は英字のみではありません
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> arr(256);
for (int i = 0; i < arr.size(); ++i) {
arr[i] = -1;
}
if (s.size() == 0) return 0;
int left = 0;
int right = 0;
int maxLen = 0;
while (right < s.size()) {
if (arr[s[right]] != -1) {
int newLeft = arr[s[right]] + 1;
while (left < newLeft) {
arr[s[left]] = -1;
left++;
}
} else {
maxLen = max(maxLen, right - left + 1);
}
arr[s[right]] = right;
right++;
}
return maxLen;
}
};