526互联

『LeetCode』3. 无重复字符的最长子串 Longest Substring Without Repeating Characters

发布时间 2023-12-22 20:10:32作者: 北岛孤影

『1』双指针算法

我的想法：
一般看到字符串子串问题想到用双指针解，看到字符串子序列问题想到用动态规划解。此题用双指针可以很快解题。

  1. 遍历字符串中的每个字符s.charAt[i], 对于每一个i，找到j使得双指针[j, i]维护的是以s.charAt[i]结尾的无重复字符的最长子串，长度为i - j + 1, 将这一长度与res的较大者更新给res。
  1. 对于每一个i，如何确定j的位置：由于[j, i - 1]是前一步得到的无重复字符的最长子串，所以如果[j, i]中有重复元素，一定是s.charAt[i]，因此右移j直到s.charAt[i]不重复为止（由于[j, i - 1]已经是前一步的最优解，此时j只可能右移以剔除重复字符s.charAt[i]，不可能左移增加字符，因此，j具有单调性、本题可用双指针算法降低复杂度）。
  2. 用数组hash记录字符s.charAt[i]在当前窗口中出现的次数，遍历过程中对于每一个i有四步操作：获取字符s.charAt[i] -> 将s.charAt[i]出现次数hash[s.charAt[i]]加1 -> 若s.charAt[i]重复则右移j（先把s.charAt[j]次数减1，再右移j） -> 确定j及更新当前长度i - j + 1给res。

实现代码：

class Solution {
    // Sliding Window
    // N is the length of s
    // Time Complexity: O(N)
    // Space Complexity: O(1)
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) return s.length();
        int res = 0;
        int[] hash = new int[127];
        for (int i = 0, j = 0; i < s.length(); i++) {
            hash[s.charAt(i)]++;
            while (hash[s.charAt(i)] > 1) --hash[s.charAt(j++)];
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
}