LeetCode longest substring without repeating characters 题解 Hash表
题目
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.
思路——Hash大法好
双指针移动。
Hash表查询字符是否出现。
时间复杂度O(L)O(L)O(L),空间复杂度O(L)O(L)O(L)
结果
Runtime: 27 ms, faster than 70.11% of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 37.5 MB, less than 100.00% of Java online submissions for Longest Substring Without Repeating Characters.
源码
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<Character>();
int ans = 0;
int l, r = 0;
Character c;
int len = s.length();
for (l = 0; l < len; ++l) {
while (r < len) {
c = s.charAt(r);
if (set.contains(c)) {
ans = Math.max(ans,r-l);
break;
} else {
set.add(c);
++r;
}
}
if (r == len) {
ans = Math.max(ans, r - l);
break;
}
set.remove(s.charAt(l));
}
return ans;
}
}
最新文章
- 日志分析 第五章 安装logstash
- 数据结构之图 Part2 - 2
- lag 和 lead
- 第七章 new的三步曲
- TODO:Half Half的设计
- HackRF实现无线门铃信号分析重放
- C# Dictionary用法总结
- Eclipse怎么显示行号,定位某行
- xcode常见错误
- 深入认识XmlReader
- deepin 开机进入 initramfs,无法开机
- Xcode自动选择证书
- 【转】EF Code First 学习笔记:约定配置
- 德卡Z90读卡器读取社保卡,德卡Z90读卡器CSharp示例程序源码
- fsck 工具 &mdash;&mdash;检查 与修复 Linux系统上的文件系统
- jquery的load()事件和ajax中load()方法的区别
- python相关参考地址收藏
- Python面试题之Python反射详解
- ZOJ 3541 The Last Puzzle(经典区间dp)
- SVN - Checksum mismatch while updating