3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Constraints:
- 0 <= s.length <= 5 * 10^4
- s consists of English letters, digits, symbols and spaces.
Example
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
思路
- 是求连续子串不是子序列
- 左右指针来截取字符串,右指针每要添加进一个字符时,先看一下当前截取字符串中是否已存在,如果存在就左指针移一位
题解
- 无脑快速AC
public int lengthOfLongestSubstring(String s) {
int left, right, result;
left = right = result = 0;
String temp;
while (right < s.length()) {
// 获取右指针字符,也就是待插入字符
String cur = String.valueOf(s.charAt(right));
// 截取当前左指针到右指针前1位的字符串
temp = s.substring(left, right);
// 当前子串中包含待插入字符,移动左指针
if (temp.contains(cur)) {
left++;
} else {
// 直到符合条件,那就算出当前子串长度
result = Math.max(result, right - left + 1);
right++;
}
}
return result;
}
- 优化
public int lengthOfLongestSubstring(String s) {
int result, left;
// 利用Set特性来简化,不依靠截取字符串函数
HashSet<Character> record = new HashSet<>();
result = left = 0;
char[] data = s.toCharArray();
// i就可以当作右指针
for (int i = 0; i < data.length; i++) {
// 如果Set中已存在当前待插入元素,返回false,那就从最左边开始移出,直到成功插入,最坏情况就是Set被清空,然后当前i成为Set中唯一元素
while (!record.add(data[i])) {
record.remove(data[left]);
left++;
}
result = Math.max(result, i - left + 1);
}
return result;
}
标签:Medium,String,int,Substring,right,result,指针,Without,left
From: https://www.cnblogs.com/tanhaoo/p/17044353.html