力扣之无重复字符的最长子串

问题 解答 1.暴力解法 算法 创建allUnique函数，如果子字符串中的字符都是唯一的，它会返回 True，否则会返回 False。遍历字符串 s 的所有可能的子字符串，更新子串长度的最大值。 时间复杂度：O(N^3) public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.Length; int ans = 0; for (int i = 0; i &lt; n; i++) { for (int j = i + 1; j &lt; 《力扣之无重复字符的最长子串》 在编程竞赛和面试中，"无重复字符的最长子串"是一个常见的问题，旨在测试对字符串处理和算法的理解。本题要求找到给定字符串中最长的子串，这个子串中没有任何重复的字符。以下是几种解决这个问题的算法方法。 1. **暴力解法**： 这种方法通过遍历字符串的所有子串来检查是否有重复字符。首先创建一个`allUnique`函数，用于判断子串中的字符是否都不同。然后，通过两层循环遍历字符串的所有可能子串，每次更新最长子串的长度。时间复杂度为O(N^3)，其中N是字符串的长度。由于其高时间复杂度，这种方法在数据量较大时效率低下，容易超时。 ```csharp public class Solution{ public int lengthOfLongestSubstring(String s){ int n = s.Length; int ans = 0; for (int i = 0; i < n; i++){ for (int j = i + 1; j <= n; j++){ if (allUnique(s, i, j)){ ans = Math.Max(ans, j - i); } } } return ans; } public bool allUnique(String s, int start, int end){ HashSet set = new HashSet(); for (int i = start; i < end; i++){ char ch = s.ElementAt(i); if (set.Contains(ch)){ return false; } set.Add(ch); } return true; } } ``` 2. **滑动窗口**： 滑动窗口是一种更为高效的解决方案，其时间复杂度为O(N)。通过维护一个由起始索引`i`和结束索引`j`定义的窗口，我们遍历字符串`s`。如果当前字符不在哈希集合`set`中，就将其添加到集合并将`j`向右移动，同时更新最长子串的长度。如果遇到重复字符，仅将`i`向右移动一位，保持窗口大小不变。这样，每个字符只被访问一次。 ```csharp public class Solution{ public int lengthOfLongestSubstring(String s){ int n = s.Length; HashSet set = new HashSet(); int ans = 0, i = 0, j = 0; while (i < n && j < n){ if (!set.Contains(s.ElementAt(j))){ set.Add(s.ElementAt(j++)); ans = Math.Max(ans, j - i); } else{ set.Remove(s.ElementAt(i++)); } } return ans; } } ``` 3. **优化滑动窗口**： 在上一种方法的基础上，我们可以进一步优化。当遇到重复字符时，不需要将`i`后移一位，而是直接跳过当前重复子串。这样，`i`的移动取决于`dic`(字典)中存储的重复字符的位置，而不是固定的后移一位。这种方法也保持了O(N)的时间复杂度。 ```csharp public class Solution{ public int lengthOfLongestSubstring(String s){ int n = s.Length, ans = 0; Dictionary dic = new Dictionary(); for (int j = 0, i = 0; j < n; j++) { if (dic.ContainsKey(s.ElementAt(j))){ i = Math.Max(dic[s.ElementAt(j)], i); } ans = Math.Max(ans, j - i + 1); dic[s.ElementAt(j)] = j + 1; } return ans; } } ``` 4. **Python实现的滑动窗口**： Python版本的滑动窗口实现与C#类似，但代码更加简洁。同样，时间复杂度为O(N)。 ```python class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 n = len(s) lookup = set() left = ans = cur_len = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > ans: ans = cur_len lookup.add(s[i]) return ans ``` 5. **优化的Python滑动窗口**： 在Python版本的滑动窗口中，可以进一步优化查找重复字符的过程。当`while`循环中检测到重复字符时，直接删除`lookup`中的旧值并更新`left`，避免了多余的减法操作。 ```python class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 lookup = set() n = len(s) left = cur_len = ans = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > ans: ans = cur_len lookup.add(s[i]) return ans ``` 以上五种方法都致力于解决“无重复字符的最长子串”问题，从暴力遍历到滑动窗口的优化，逐步提高了算法的效率。在实际应用中，优化的滑动窗口算法是首选，因为它在保证正确性的同时，具有较高的时间效率。