Longest Substring Without Repeating Characters
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.
题目大意及分析
这个题目是寻找最长的不重复的子串，而不是字符的序列（数一下字符串中的不同字符的个数）看前两个例子很容易有这样的误会。
我一开始就很简单的用了一个map判断，有则继续执行，没有则添加，输出个数。
//题目的理解就有问题
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();int ans = 0;Map<Character, Integer> map = new HashMap<>(); for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
continue;}else{
map.put(s.charAt(j),ans);ans++;} }return ans;}
}
我又想了好久实现了一下，感觉太过暴力，不美观，故看了官方的题解，学习下思路。
大神的代码，思路是使用滑动窗口，来判断最大的子串，使用 ans 来存贮每一次比较中最长的子串长度，用 i 来保存出现重复是最候一次出现的次数（因为最后一个重负的 char 也是下一个字符串的开始）当出现相同的时候，则判断 i 的位置，因为可能连续出现很多个重复，所以，要用最后一个代替。
我觉着比较难思考的地方是 i 值的计算。
类似 abbbbbabc：
- 第一个 a 和第一个 b 都是没有出现过的，i == 0；
- 从第二个 b 开始连续四个 b 都是重复的值，每一次都是使用上一次 b 的 value 来代替 i 。
- 当检测到第二个 a 时，s.charAt(j) 的值是1（第一个 a 的位置），这个时候 i 的值应该还是上一个 i 的值，即为5，因为上一个 char 算是一个新的字符串的开始。
- 当第六个 b 出现时，s.charAt(j) 的值是6（第五个 b 的位置）
ans = 上一个 ans 和 ( j - i + 1 ) 中较大的值。
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| key | a | b | b | b | b | b | a | b | c |
| value | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| i | 0 | 0 | 2 | 3 | 4 | 5 | 5 | 6 | 6 |
| ans | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 |
代码实现
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;Map<Character, Integer> map = new HashMap<>(); // current index of character// try to extend the range [i, j]for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
//当重复时，map取的是已出现的字符中最后一次出现的位置，若与前一个字符不同，则说明是下一个字符串//此时i还是上一次循环中的i，若与上一个字符串相同，则用上一个字符串的value代替//故，i的值是上一次的i和本次出现的字符对应的value中的较大的值i = Math.max(map.get(s.charAt(j)), i);}//因为i一直是在变的，所以j-i+1的值只有在出现新的更长的字符串时才会代替ansans = Math.max(ans, j - i + 1);//加入map，下一次判断的时候则get最后一次加入的valuemap.put(s.charAt(j), j + 1);}return ans;}
}
总结
刷题，我觉着这种比较有效的思维和解题思路对我启发很大。这个滑动窗口的时间复杂度是O(N)，比我的两三重循环省了很多的时间。果然一定要深究各种技巧。加油加油。