欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

无重复字符的最长子串

程序员文章站 2024-03-19 19:09:04
...

今天做第三题,无重复字符的最长字串,看着很简单,暴力求解,但是运行效率很差。

题目:

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

示例 1:

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

示例 2:

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

示例 3:

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

废话不多说,先上我的菜鸡解题思路(字太丑不要介意):

无重复字符的最长子串

觉得我的字看不下去的就看下面的文字吧:
(1)定义两个变量maxLength(存放最长字串长度) 和 str(存放临时的字串);

(2)遍历入参字符串;

(3)如果遍历到的字符在str中存在,获取该字符下标,如果子串长度大于maxLength,maxLength就是当前子串长度,而str就是字符下标之后的字符串加上最新的字符;

(4)如果字符不存在str中,str就再拼接上遍历的字符,如果子串长度大于maxLength,maxLength就是当前子串长度。

 

好了,下面是代码:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        String str = "";
        for(int i = 0;i < s.length();i ++)
        {
            char newChar = s.charAt(i);
            if(str.contains(Character.toString(newChar)))
            {
                int index = str.indexOf(newChar);
                if(str.length() > maxLength)
                {
                    maxLength = str.length();                   
                }
                str = str.substring(index+1)+Character.toString(newChar);
            }
            else
            {
                str = str + newChar;     
                if(str.length() > maxLength)
                {
                    maxLength = str.length();
                }           
            }
        }
               
        return maxLength;
    }
}

提交了一下,结果很惨。。。。。。。。。。。。。

执行用时 :20 ms, 在所有 Java 提交中击败了24.55%的用户

内存消耗 :40.7 MB, 在所有 Java 提交中击败了5.01%的用户

 

看了看官方提供的方法,使用的是滑动窗口法。

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)(左闭,右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i, j) 向右滑动 1 个元素,则它将变为 [i+1, j+1)(左闭,右开)。

回到我们的问题,我们使用 HashSet 将字符存储在当前窗口 [i, j)(最初 j = i)中。 然后我们向右侧滑动索引 j,如果它不在HashSet 中,我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。此时,我们找到的没有重复字符的最长子字符串将会以索引 i开头。如果我们对所有的 i 这样做,就可以得到答案。

代码如下:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

执行用时 :9 ms, 在所有 Java 提交中击败了69.81%的用户

内存消耗 :40 MB, 在所有 Java 提交中击败了5.42%的用户

 

上述的方法最多需要执行 2n 个步骤。事实上,它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射,而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时,我们可以立即跳过该窗口。

也就是说,如果 s[j]在 [i, j)范围内有与 j'重复的字符,我们不需要逐渐增加 i。 我们可以直接跳过 [i,j']范围内的所有元素,并将 i变为 j' + 1。

优化后的滑动窗口:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

执行用时 :7 ms, 在所有 Java 提交中击败了82.96%的用户

内存消耗 :39.7 MB, 在所有 Java 提交中击败了6.86%的用户

加快了2ms,还是挺不错的。

好了,今天的分享就到这里了,欢迎留言评论你的思路和想法。

相关标签: 每日一题