力扣 3.无重复字符的最长子串——Java

题目要求：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

题解：

import java.util.Arrays;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 检查字符串是否为空或长度为0
        if (s == null || s.length() == 0) {
            return 0; // 如果是空字符串，返回0
        }
        
        // 将字符串转换为字符数组
        char[] arr = s.toCharArray();
        
        // 用于记录每个字符出现次数的数组
        int[] n = new int[1000]; // 假设字符集的大小足够大

        int result = 0; // 记录最长无重复字符子串的长度
        int j = 0; // 滑动窗口的起始位置

        // 遍历字符数组
        for (int i = 0; i < arr.length; i++) {
            n[arr[i]]++; // 记录当前字符的出现次数
            
            // 如果当前字符出现次数超过1，表示有重复字符
            while (n[arr[i]] > 1) {
                n[arr[j]]--; // 减少起始字符的计数
                j++; // 移动起始位置以排除重复字符
            }
            
            // 更新最长无重复字符子串的长度
            result = Math.max(result, i - j + 1);
        }
        
        return result; // 返回最长无重复字符子串的长度
    }
}

代码解释

1. 空字符串检查：

   if (s == null || s.length() == 0) {
       return 0;
   }
   

   • 如果输入字符串 s 为空或长度为 0，直接返回 0，因为没有可处理的字符。

2. 字符串转化为字符数组：

   char[] arr = s.toCharArray();
   

   • 将字符串 s 转换为字符数组 arr，以便于后续处理。

3. 字符计数数组：

   int[] n = new int[1000];
   

   • 创建一个整型数组 n 用于记录每个字符的出现次数。这里假设字符集的大小足够大（如 ASCII 字符集）。

4. 初始化变量：

   int result = 0; // 最长无重复子串的长度
   int j = 0; // 滑动窗口的起始位置
   

5. 遍历字符数组：

   for (int i = 0; i < arr.length; i++) {
       n[arr[i]]++; // 记录当前字符的出现次数
   

   • 使用 for 循环遍历字符数组 arr，并增加当前字符的计数。

6. 处理重复字符：

   while (n[arr[i]] > 1) {
       n[arr[j]]--; // 减少起始字符的计数
       j++; // 移动起始位置以排除重复字符
   }
   

   • 如果当前字符的计数大于 1，说明出现了重复字符，则进入 while 循环，减少 arr[j] 的计数，并移动 j，以确保窗口内的字符都是唯一的。

7. 更新最长无重复子串长度：

   result = Math.max(result, i - j + 1);
   

   • 计算当前无重复子串的长度（i - j + 1），并更新 result，保持记录最长的长度。

8. 返回结果：

   return result;
   

   • 方法结束时返回最长无重复字符子串的长度 result。

注意事项

• 数组越界：在 for 循环中，arr.length() 应为 arr.length，因为 arr 是字符数组，不是字符串。
• 字符集大小：int[] n = new int[1000]; 假设字符集足够大，实际上对于 ASCII 字符集，可以使用 int[128] 或 int[256] 来节省空间。

示例输入

假设我们的输入字符串是：

s = "abcabcbb"

初始化

1. 字符数组转换：

   char[] arr = s.toCharArray(); // arr = ['a', 'b', 'c', 'a', 'b', 'c', 'b', 'b']
   

2. 字符计数数组：

   int[] n = new int[1000]; // 用于记录字符出现次数
   

3. 初始化变量：

   int result = 0; // 最长无重复子串长度
   int j = 0; // 滑动窗口的起始位置
   

遍历字符数组

我们将逐步遍历字符数组 arr，并记录字符出现的次数，同时更新最长无重复子串的长度。

过程演示

1. i = 0，字符 arr[0] = 'a'：

   • n['a']++ -> n['a'] = 1
   • result = Math.max(result, 0 - 0 + 1) = 1 （当前子串 “a”）

2. i = 1，字符 arr[1] = 'b'：

   • n['b']++ -> n['b'] = 1
   • result = Math.max(result, 1 - 0 + 1) = 2 （当前子串 “ab”）

3. i = 2，字符 arr[2] = 'c'：

   • n['c']++ -> n['c'] = 1
   • result = Math.max(result, 2 - 0 + 1) = 3 （当前子串 “abc”）

4. i = 3，字符 arr[3] = 'a'：

   • n['a']++ -> n['a'] = 2 （出现重复）
   • 进入 while循环，n[‘a’] > 1：
     • 第一次循环：
       • n['a']-- -> n['a'] = 1
       • j++ -> j = 1 （窗口变为 “bc”）
     • 第二次检查 while 条件：n['a'] > 1 不成立，跳出循环。
   • result = Math.max(result, 3 - 1 + 1) = 3 （当前子串 “abc”）

5. i = 4，字符 arr[4] = 'b'：

   • n['b']++ -> n['b'] = 2 （出现重复）
   • 进入 while循环，n[‘b’] > 1：
     • 第一次循环：
       • n['b']-- -> n['b'] = 1
       • j++ -> j = 2 （窗口变为 “c”）
     • 第二次检查 while 条件：n['b'] > 1 不成立，跳出循环。
   • result = Math.max(result, 4 - 2 + 1) = 3 （当前子串 “abc”）

6. i = 5，字符 arr[5] = 'c'：

   • n['c']++ -> n['c'] = 2 （出现重复）
   • 进入 while循环，n[‘c’] > 1：
     • 第一次循环：
       • n['c']-- -> n['c'] = 1
       • j++ -> j = 3 （窗口变为 “a”）
     • 第二次检查 while 条件：n['c'] > 1 不成立，跳出循环。
   • result = Math.max(result, 5 - 3 + 1) = 3 （当前子串 “abc”）

7. i = 6，字符 arr[6] = 'b'：

   • n['b']++ -> n['b'] = 2 （出现重复）

   • 进入 while循环，n[‘b’] > 1

     ：

     • 第一次循环：
       • n['a']-- -> n['a'] = 0
       • j++ -> j = 4 （窗口变为 “b”）
     • 第二次检查 while 条件：n['b'] > 1 不成立，跳出循环。

   • result = Math.max(result, 6 - 4 + 1) = 3 （当前子串 “bc”）

8. i = 7，字符 arr[7] = 'b'：

   • n['b']++ -> n['b'] = 3 （出现重复）
   • 进入 while循环，n[‘b’] > 1：
     • 第一次循环：
       • n['b']-- -> n['b'] = 2
       • j++ -> j = 5 （窗口变为 “c”）
     • 第二次检查 while 条件：n['b'] > 1 不成立，跳出循环。
   • result = Math.max(result, 7 - 5 + 1) = 3 （当前子串 “bc”）

最终结果

在遍历完整个字符串后，result 的值是 3，表示最长无重复字符子串的长度为 3（例如 “abc”）。