LeetCode 3. Longest Substring Without Repeating Characters 原创Java参考解答
问题描述
https://leetcode.com/problems/longest-substring-without-repeating-characters/
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
解题思路
题目是求字符串中最长的无重复字符串的长度。
快慢指针O(N)解法：快指针j、慢指针i。
快指针 j 检查 j 位置字符是否在在HashSet中
- 不在的话，就继续向右移动 j 指针， 并更新最大长度。
- 若在的话，则删除HashSet头部字符，即 i 所在位置字符，并移动 i 指针。
参考代码
public class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0;
int j = 0;
int longest = 0;
HashSet<Character> set = new HashSet<>();
while (j < s.length()) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
longest = Math.max(longest, set.size());
} else {
set.remove(s.charAt(i++));
}
}
return longest;
}
}