题目链接：点击打开链接
题目大意：略
解题思路
相关企业
- 字节跳动
- 亚马逊（Amazon）
- 微软（Microsoft）
- 苹果（Apple）
- 谷歌（Google）
- 彭博（bloomberg）
- 华为
- 优步（Uber）
- VMware
AC 代码
- Java
// 解决方案(1) class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> dic = new HashMap<>(); int res = 0, tmp = 0, len = s.length(); for(int j = 0; j < len; j++) { int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i dic.put(s.charAt(j), j); // 更新哈希表 tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j] res = Math.max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } } // 解决方案(2) class Solution { public int lengthOfLongestSubstring(String s) { int res = 0, tmp = 0, len = s.length(); for(int j = 0; j < len; j++) { int i = j - 1; while(i >= 0 && s.charAt(i) != s.charAt(j)) i--; // 线性查找 i tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j] res = Math.max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } } // 解决方案(3) class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> dic = new HashMap<>(); int i = -1, res = 0, len = s.length(); for(int j = 0; j < len; j++) { if(dic.containsKey(s.charAt(j))) i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i dic.put(s.charAt(j), j); // 哈希表记录 res = Math.max(res, j - i); // 更新结果 } return res; } } // 解决方案(4) class Solution { public int lengthOfLongestSubstring(String s) { int res = 0; Set<Character> set = new HashSet<>(); Queue<Character> queue = new LinkedList(); int len = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (set.contains(c)) { res = Math.max(res, len); while (queue.peek() != c) { set.remove(queue.poll()); len--; } // 第一次碰到相同字符 或 循环最后一次的删除 set.remove(queue.poll()); len--; // 加上本次字符 set.add(c); queue.add(c); len++; continue; } set.add(c); queue.add(c); len++; res = Math.max(res, len); } return res; } }
- C++
// 解决方案(1) class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, int> dic; int res = 0, tmp = 0, len = s.size(), i; for(int j = 0; j < len; j++) { if(dic.find(s[j]) == dic.end()) i = - 1; else i = dic.find(s[j])->second; // 获取索引 i dic[s[j]] = j; // 更新哈希表 tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j] res = max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } }; // 解决方案(2) class Solution { public: int lengthOfLongestSubstring(string s) { int res = 0, tmp = 0, len = s.size(); for(int j = 0; j < len; j++) { int i = j - 1; while(i >= 0 && s[i] != s[j]) i--; // 线性查找 i tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j] res = max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } }; // 解决方案(3) class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, int> dic; int i = -1, res = 0, len = s.size(); for(int j = 0; j < len; j++) { if(dic.find(s[j]) != dic.end()) i = max(i, dic.find(s[j])->second); // 更新左指针 dic[s[j]] = j; // 哈希表记录 res = max(res, j - i); // 更新结果 } return res; } };
