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

发布于:2024-10-18 ⋅ 阅读:(33) ⋅ 点赞:(0)

题目要求:

给定一个字符串 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”)。


网站公告

今日签到

点亮在社区的每一天
去签到