[3] Longest Substring Without Repeating Characters
- 字符串问题: 练习双指针,hash表
-
参考: yxc
-
题目:
/*
* @lc app=leetcode id=3 lang=cpp
*
* [3] Longest Substring Without Repeating Characters
*
* https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
*
* algorithms
* Medium (28.72%)
* Likes: 6296
* Dislikes: 358
* Total Accepted: 1.1M
* Total Submissions: 3.8M
* Testcase Example: '"abcabcbb"'
*
* 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.
*
*
*
*
*
*/
- 第一次做:TLE
/*
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
for (int i =0; i < s.size(); i ++ )
{
int j = i;
// 这里出错,i~j区间,不仅仅是最后一个和第一个不同,而是所有的字符都不相同
while (j < s.size() && s[j] != s[i]) j ++ ;
i = j - 1;
res = max(res, j - i + 1);
}
return res;
}
};
- c++ 代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hash; //hash表存char和对应char的个数
int res = 0;
//双指针:先让i= 0, j向后走
for (int i = 0, j = 0; j < s.size(); j ++ )
{
//向hash表里面添加
//若查找的key不存在,则只想hash[key]之后,hash会自动新建一个二元数组(key,zero)
//并返回zero的引用,这里的zero可以代表0.空字符串等
hash[s[j]] ++ ; // j向后走的时候,对应char的个数加一
// 当hash表中出现个数大于1的char时,i开始向后走,直到所有char个数都为1
while (hash[s[j]] > 1)
{
hash[s[i]] -- ; // 减去是s[i]的个数
i ++ ; // i 向后走
}
res = max(res, j - i + 1);
}
return res;
}
};
- hash表扩展
// 如何用hash表统计字符串出现的个数?
// 给定n个字符串,m个问题,每个问题询问一个字符串出现的次数
// 每个字符串长度不超过25
// n, m <= 20000
unordered_map<char, int> hash;
char str[25];
for (int i = 1; i <= n; i ++ )
{
scanf("%s", str);
h[str] ++ ;
}
for (int i = 1; i <= m; i ++ )
{
scanf("%s", str);
if (hash.find(str) == h.end()) puts("0");
// hash.find(key) 返回指向该二元组的迭代器
else printf("%d\n", h[str]);
}