【每日一题】LeetCode #3 无重复字符的最长字串

晓

发布于 2020-04-06

在计算机领域，算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始，跟随我每天刷一道算法题吧！

在此之前，我们刷的几乎都是有关数组操作的算法题。在接下来的几天里，我们将学习 “双指针技巧”，它可以帮助我们解决许多与数组相关的问题。

双指针专题第六天。

LeetCode #3 无重复字符的最长字串

题目

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

示例1：

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

示例2：

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

示例3：

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

解题思路

滑动窗口思路 1：

今天继续双指针应用——滑动窗口算法。这一道题不是对数组的操作，而是对字符串的操作。但是，字符串实际上是一个 unicode 字符数组。我们可以对它执行几乎所有的数组操作。

这一题依然是求解连续的元素，所以毫无疑问可以使用滑动窗口。滑动窗口常规思路就是一步步遍历数组，左指针缩小窗口，右指针扩大窗口，遍历出所有的窗口的可能性。（与前两天的思路差不多，我就不细说了。）

滑动窗口思路 1代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int left = 0;
        int right = 0;
        int maxSize = 0;
        // 存放连续的字符，排除重复字符
        Set<Character> chars = new HashSet<>();
        
        while (right < length && left < length){
            if (!chars.contains(s.charAt(right))){
                // 添加字符，扩大窗口，计算当前最大长度
                chars.add(s.charAt(right++));
                maxSize = Math.max(maxSize, right - left);
            }else{
                // 删除最前面的字符，缩小窗口
                chars.remove(s.charAt(left++));
            }
        }
        return maxSize;
    }
}

滑动窗口思路 2：

上面的思路是遍历了所有窗口可能的情况，很明显有些地方是多余的。在我们找到重复元素时，左指针应该直接跳过重复元素前面的元素，因为遍历它们是没有意义的。所以，我们对上面的思路进行了优化。

滑动窗口代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        
        for (int left = 0, right = 0; right < n; right++) {
            if (map.containsKey(s.charAt(right))) {
                // 左指针跳过重复元素前面的元素
                left = Math.max(map.get(s.charAt(right)), left);
            }
            ans = Math.max(ans, right - left + 1);
            map.put(s.charAt(right), right + 1);
        }
        return ans;
    }
}

【每日一题】LeetCode #141 环形链表

在计算机领域，算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始，跟随我每天刷一道算法题吧！在此之前，我们刷的几乎都是有关数组操作的...

【每日一题】LeetCode #485 最大连续 1 的个数