LeetCode 0003 - Longest Substring Without Repeating Characters
# Hints
- 双指针扫描
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
# 题意
给定一个字符串,求其最长子串的长度,满足子串内任意两个字符不相同。
# 题解
双指针扫描的经典问题。
具体地讲,我们维护 为当前答案,不断令 递进直到发现当前答案不合法,此时再不断令 递进直到发现答案恢复合法,在此过程中更新答案,重复直到遍历完成即可。
细节问题:
- 注意特判空串,但我的代码实现其实可以不需要特判。
# AC代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 特判
if (s.empty()) {
return 0;
}
// 初始化
bool used[256];
memset(used, false, sizeof(used));
// 主循环
int res = 0;
int left = 0, right = 0;
while (right < s.length()) {
// 递进
while (used[s[right]]) {
used[s[left]] = false;
left ++;
}
used[s[right]] = true;
// 更新答案
res = max(res, right - left + 1);
// 递进
right ++;
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01