Java LeetCode题解之Longest Substring Without Repeating（无重复字符的最长子串）
在编程世界中，算法题目往往是检验程序员基本功的试金石。LeetCode作为一个著名的算法练习平台，提供了大量丰富的题目供程序员们挑战。今天我们要探讨的是LeetCode上的一个经典题目——“Longest Substring Without Repeating Characters（无重复字符的最长子串）”。
这个问题要求我们在给定的字符串中找到不含重复字符的最长子串的长度。一个子串是字符串中连续的一段字符，而解决这个问题的常用方法有两种：暴力法和滑动窗口法。
暴力法的思路很直观，就是去遍历所有可能的子串，然后检查每个子串是否包含重复字符。显然，这种方法的时间复杂度非常高，为O(n^3)，因此它不是解决这个问题的最优解。
滑动窗口法则是更为高效的一种解法，其时间复杂度为O(n)，空间复杂度为O(min(m,n))，其中m是字符集的大小，n是字符串的长度。滑动窗口法的基本思想是创建一个窗口，该窗口可以向右滑动，但窗口内的字符是唯一的，即没有重复。随着窗口的滑动，一旦遇到重复字符，就将窗口的左边界向右移动，直到窗口内再次没有重复字符为止。在此过程中，记录下最长无重复字符子串的长度。
在Java实现中，我们可以使用HashSet来辅助判断窗口内是否有重复字符。当添加一个新字符到窗口时，如果该字符已经存在于HashSet中，则需要移除HashSet中的某些字符，直到重复的字符被移除。具体实现时，我们还需要一个变量来记录遇到的最大长度，并在每次窗口更新时与当前最大长度进行比较。
下面是使用滑动窗口法解决问题的一个Java代码示例：
```java
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int maxLen = 0;
for (int start = 0, end = 0; end < s.length(); end++) {
char currentChar = s.charAt(end);
if (map.containsKey(currentChar)) {
start = Math.max(map.get(currentChar), start);
}
maxLen = Math.max(maxLen, end - start + 1);
map.put(currentChar, end + 1);
}
return maxLen;
}
}
```
在这段代码中，我们使用了HashMap来存储当前字符在子串中的位置索引。当遇到重复字符时，更新窗口的起始位置。maxLen变量用于记录当前无重复字符子串的最大长度。每次循环结束后，都将当前子串长度与maxLen进行比较，并取较大的值。
通过以上方法，我们可以高效地解决LeetCode中的这个问题，并且对于类似的字符串处理问题也能有一个清晰的处理思路。
