美文网首页
LeetCode第三题:无重复字符的最长子串

LeetCode第三题:无重复字符的最长子串

作者: 躺在家里干活 | 来源:发表于2019-10-08 09:47 被阅读0次

题目

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

说明

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

一般思路

  1. 将字符串转化为字符数组
  2. 问题转化:
  • 找出相同字符之间的下标差,并且后一个字符之前不能有相同的字符
    abcdb中字符串abcdbcd符合要求;
    abcdbefb中字符串bcdbef不符合要求,因为bcdbef中在最后一个字符b之前,有相同的字符b,但是子串bef是符合要求的;

  • 找出最大的下标差

  1. 简单思路
  • 循环整个数组
  • 在每次循环中保存一个key(具体字符):value(下标),并且判断之前是否保存过这个字符
  • 如果保存过,先判断两个下标之间是否有相同的字符,如果有就需要处理这种情况(取到没有重复字符的下标位置),之后计算当前下标到之前保存的下标之间的距离
  • 如果字符没有保存过,就保存字符
public static int getNoRepeat(String s) {
        char[] chars = s.toCharArray();
        // 用来保存 字符:下标
        Map<Character, Integer> map = new HashMap<>();
        // 最长无重复字符的子串长度
        int maxLong = 0;
        // 当前可用的下标
        // 对于[abcdedf]
        // 当下标是0至4的时候,effectiveIndex = -1
        // 当下标到5(字符d)的时候,effectiveIndex = 3 (因为前一个d的坐标是3)
        int effectiveIndex = -1;
        // 每次循环的最大值
        int tempMax = 0;
        for (int i = 0; i < chars.length; i++) {
            // 获取下标
            int mapValue = map.getOrDefault(chars[i], -1);
            // -1 表示map中没有当前字符
            if (mapValue == -1) {
                tempMax = i - effectiveIndex;
            } else {
                // 如果map中有这个字符,并且这个字符的小标大于 effectiveIndex
                // [abcdefda] 中,当循环到第二个字符a的时候,map的值是0,但是effectiveIndex为3,此时不需要更改effectiveIndex
                // [abcdefxdxyz] 中,当循环到第二个x时,e12x = 3,此时mapValue = 6,需要更换e12x,否则子串中符号x会重复
                if (mapValue > effectiveIndex) {
                    tempMax = i - mapValue;
                    effectiveIndex = mapValue;
                } else {
                    tempMax = i - effectiveIndex;
                }
            // 判断此次的长度是否大于当前最大长度
            if (tempMax > maxLong) {
                maxLong = tempMax;
            }
            // 向map中增加元素
            map.put(chars[i], i);
        }
        return maxLong;
    }

执行之后,击败76% 😣

优化思路

想着是因为map存取的时候消耗了性能,使用数组+ASCII码的方式替换写法

public static int getNoRepeat(String s) {
        char[] chars = s.toCharArray();
        int[] map = new int[129];
        for (int i = 0; i < map.length; i++) {
            map[i] = -1;
        }
        int maxLong = 0;
        int effectiveIndex = -1;
        int tempMax;
        for (int i = 0; i < chars.length; i++) {
            int key = chars[i];
            int index = map[key];
            // 有值,说明可以更新
            if (index > effectiveIndex) {
                effectiveIndex = index;
            }
            tempMax = i - effectiveIndex;
            if (tempMax > maxLong) {
                maxLong = tempMax;
            }
            map[key] = i;
        }
        return maxLong;
    }

执行代码,击败99.39%

打完收工

更多说明

ASCII的应用可能会让人觉得知识凑巧,万一有汉字,其它特殊字符怎么办,其实这就是一种思路,只要元素是已经的,有限的,就可以使用这种思路,如果会有特殊字符,我们也可以自定义特殊字符对应的数值。

其他语言解法

1. JS

// 方法一
var lengthOfLongestSubstring = function(s) {
    var effectIndex = -1;
    var len = 0;
    var map = [];
    for (var j = 0; j < 129; j++) {
        map[j] = -1;
    }
    for (var i = 0; i < s.length; i++) {
        var key = s[i].charCodeAt();
        var index = map[key];
        if (index > effectIndex) {
            effectIndex = index;
        }
        len = len > i - effectIndex ? len : i - effectIndex
        map[key] = i
    }
    return len
};
// 方法二
var lengthOfLongestSubstring = function(s) {
    var str = '';
    var len = 0;
    for (var i = 0; i < s.length; i++) {
        var index = str.indexOf(s[i])
        if (index > -1) {
            str = str.slice(index + 1);
        }
        str += s[i];
        len = len > str.length ? len : str.length
    }
    return len
};

2. Python

def lengthOfLongestSubstring(self, s: str) -> int:
    # 声明字典,Python中要是用字典做这种查询,数组很慢
    arr = {}
    max_length = 0
    effective_index = -1
    for (index, char) in enumerate(s):
        # 是否需要改变effective_index
        if char in arr and arr[char] > effective_index:
            effective_index = arr[char]
        temp_length = index - effective_index
        if temp_length > max_length:
            max_length = temp_length
        arr[char] = index
    return max_length

# 执行用时 :
# 64 ms
# 在所有 Python3 提交中击败了
# 99.38%
# 的用户

# 可见python和java速度上不是一个重量级的对手
# 以后有时间 写上C的代码

点击查看更多源码

直通车

LeetCode第三题直达车

我的个人博客,有空来坐坐

相关文章

网友评论

      本文标题:LeetCode第三题:无重复字符的最长子串

      本文链接:https://www.haomeiwen.com/subject/isdkuctx.html