当前位置：
  1. 首页
  2. 剑指offer刷题第二期
  3. 问题详情

【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串

本问题对应课程链接：剑指offer刷题第二期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路
2、给出时间和额外空间复杂度

shuaidi
115 12

共以下 12 个回答

  • Gg 普通 2023年8月8日 下午10:54 
    class Solution {
    // 利用HashMap存储左指针
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> dic = new HashMap<>();
        int res = 0;
        // 默认要为-1，index - (-1) 才为长度
        int left = -1;
        for(int j = 0; j < s.length(); j ++){
            Character curr = s.charAt(j);
            if(dic.containsKey(curr)){
                // 左指针也需要一直向右移
                left = Math.max(left,dic.get(curr));
            }
            dic.put(curr,j);
            res = Math.max(res,j-left);
        }
        return res;
    }
}
    0 赞同 0 条回复
  • 宁 永久会员 2023年3月14日 下午3:32

    containsKey而不是contains

    class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        //不含重复字符的最长子字符串————
        //递推关系式，比较上一次这个字母出现的位置差 和 前一个最大连续字符串长度，取小的
        //用map记录是否出现过，出现的位置
        Map<Character, Integer> map = new HashMap<>();
        map.put(s.charAt(0), 0);
        int dp = 1;
        int max = 1;
        for(int i = 1; i < s.length(); i ++){
            if(!map.containsKey(s.charAt(i))){
                dp = dp + 1;
            }else{
                int k = map.get(s.charAt(i));
                dp = Math.min(dp + 1, i - k);
            }
            max = Math.max(max, dp);
            map.put(s.charAt(i), i);
        }
        return max;
    }
}
    0 赞同 0 条回复
  • PatNick 普通 2023年1月19日 上午9:35 
    # 单变量dp
def lengthOfLongestSubstring2(s: str) -> int:
    if not s:
        return 0

    # 以字符s[i]结尾时，不重复子串长度为dp[i]
    dp = 1

    # 存放字符串的字符和索引的对应关系的
    map = {s[0]:0}
    res = 1
    for _ in range(1,len(s)):
        if not s[_] in map.keys():
            dp = dp + 1
        else:
            # 如果当前值已经遍历过了
            # 找到上一个出现这个值的索引
            k = map.get(s[_])

            # _ - k表示当前值与和它最近的相等的数之间的距离，如果这个距离大于dp[_-k],说明上一个重复的数是在组成dp[_-1]这个情况的子串内的，那dp[_]就要更新
            # 如果这个距离小于dp[_-k],说明上一个重复的数是在组成dp[_-1]这个情况的子串外的，那dp[_] = dp[_-1] + 1
            dp = _ - k if _ - k <= dp else dp + 1

        res = max(res,dp)
        map[s[_]] = _


    return res
    0 赞同 0 条回复
  • lucca 普通 2023年1月18日 下午2:09

    双指针

    • 时间复杂度O(N)
    • 空间复杂度O(N)
    class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n < 2) return n;

        // 队列, 存储最长子字符串
        int[] q = new int[n];
        int hh = 0, tt = -1;
        // 可能不全是小写英文字符, 用map(吐槽一下Java的Map不咋好用)
        Map pos = new HashMap();

        int max = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            // 查找这个字符上一次出现的位置
            int oldP = pos.getOrDefault(c, -1);
            // 如果存好的子串包含了上一次出现的s[i], 则s[i]及之前都要舍弃
            while (hh <= tt && oldP >= q[hh]) hh++;
            // 把当前字符放进字串
            q[++tt] = i;
            // 更新最大长度
            max = Math.max(max, q[tt] - q[hh] + 1);
            // 更新s[i]上一次出现的位置
            pos.put(c, i);
        }
        return max;
    }
}

    更简单的写法

    class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) last[i] = -1;

        int n = s.length(), max = 0, st = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            st = Math.max(st, last[c] + 1);
            max = Math.max(max, i - st + 1);
            last[c] = i;
        }
        return max;
    }
}
    0 赞同 0 条回复
  • @ 普通 2022年12月20日 上午11:15

    时间复杂度：O(N)

    空间复杂度：O(1)

    思路:从第一个元素开始向左遍历，每遍历一个元素用就把它加入list，如果list已有这个元素（假设这个元素是a），就对list里的元素进行删除，删除的元素为从第一个元素开始直到删除a位置，然后在对剩余元素的list的个数进行判断，看它是否大于max.

    class Solution {
    public int lengthOfLongestSubstring(String s) {
        List<Character> list = new ArrayList<Character>();
        int max = 0;

        for (int i = 0; i < s.length(); i++) {

            char cur = s.charAt(i);

            if (list.contains(cur)) {
                while (true) {
                    Character rc = list.remove(0);

                    if (rc == cur)
                        break;
                }

            }
            list.add(cur);

            max = list.size() > max ? list.size() : max;
        }

        return max;

    }

}
    0 赞同 0 条回复
  • 🚲南下 普通 2022年12月3日 下午6:14 
    class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        int ans = 0;
        unordered_map<char, int> mp;
        for(int i = 0, j = 0; i < s.size(); i++)
        {
            mp[s[i]]++;
            while(j < i && mp[s[i]] > 1) mp[s[j++]]--; //遇到相同的字符，则j++
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};
    0 赞同 0 条回复
  • T 普通 2022年11月30日 下午10:33 
    class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0, tmp = 0;
        //当前位置的最大子串长度
        for(int i = 0; i < s.length(); i++) {
            int index = map.getOrDefault(s.charAt(i), -1);
            map.put(s.charAt(i), i);
            // 如果当前i位置和重复元素index的距离大于子串长度说明重复字符在子串之外
            tmp = tmp < i - index ? tmp + 1 : i - index;
            res = Math.max(res, tmp);
        }
        return res;
    }
}
    0 赞同 0 条回复
  • Tolkien 永久会员 2022年11月29日 下午6:56 
    /**
     * 动态规划+哈希表
     * 时间复杂度：O(n)，空间复杂度：O(1)
     * 1. 以s[n]结尾的最长的不包含重复字符的子字符串长度为dp[n]
     * 2. 如果第i个字符与前面字符若不重复，则dp[i] = dp[i-1]+1
     * 若重复，则dp[i] = dp[i-1] >= i-map.get(ch) ? i-map.get(ch) : dp[i-1]+1;
     * 3. dp[0] = 1
     */
    public static int lengthOfLongestSubstring(String s) {
        if (s.length() <= 0) {
            return 0;
        }

        int[] dp = new int[s.length()];
        dp[0] = 1;

        HashMap<Character, Integer> characters = new HashMap<>();
        characters.put(s.charAt(0), 0);

        int res = dp[0]; // 全局 "最长不重复子字符串"
        for (int i = 1; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!characters.containsKey(ch)) {
                dp[i] = dp[i-1]+1;
            }
            else {
                int index = characters.get(ch);
                dp[i] = dp[i-1] >= i-index ? i-index : dp[i-1]+1;
            }
            characters.put(ch, i);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
    0 赞同 0 条回复
  • 西西弗斯的石头 永久会员 2022年11月27日 下午12:14

    时间空间复杂度为O（n）

    class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() <= 0){
            return 0;
        }
        Map<Character,Integer> map = new HashMap<>();
        map.put(s.charAt(0),0);
        int a = 1;
        int res = 1;
        for(int i = 1;i < s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                a = a + 1;
            }else{
                int k = map.get(s.charAt(i));
                a = i - k > a ? a+1:i - k; 
            }
            res = Math.max(res,a);
            map.put(s.charAt(i),i);
        }
        return res;
    }
}
    0 赞同 0 条回复
  • 青木 普通 2022年11月25日 下午9:24 
    /** 
    用滑动窗口
    第一时间想到的确实是这个办法，但是不晓得怎么实现，继续交学费0.0

    时间O(n)
    空间O(1)
 */

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dict = new HashMap<>();

        int i = -1, res = 0;
        for(int j=0; j<s.length(); j++){
            if(dict.containsKey(s.charAt(j))){
                i = Math.max(i, dict.get(s.charAt(j)));
            }
            dict.put(s.charAt(j), j);
            res = Math.max(res, j-i);
        } 
        return res;
    }
}
    0 赞同 0 条回复
  • Mooby 普通 2022年11月25日 下午6:54 
    class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() <= 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int a = 1;
        map.put(s.charAt(0), 0);
        int res = 1;
        for (int i = 1; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) {
                a += 1;
            } else {
                int k = map.get(s.charAt(i));
                a = i - k <= a ? i - k : a + 1;
            }
            res = Math.max(res, a);
            map.put(s.charAt(i), i);
        }
        return res;
    }
}

    时间：O(n)，空间：O(n)

    0 赞同 0 条回复
  • 訁訁訁訁訁 普通 2022年11月24日 下午11:41

    空间复杂度O(N)时间复杂度O(N)

    /*
①dp[i]:以下标i结尾的不重复子串的长度为dp[i]
②关系式：没有在左侧区间出现过，或者在区间之外：dp[i]=dp[i-1]+1
左侧区间出现过:dp[i]=i-k(字符上一次出现位置)
哈希表字符和下标的映射
*/
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() <= 0) return 0;
        int len = s.length();
        Map<Character,Integer> map = new HashMap<>();
        int[] dp = new int[len];
        dp[0] = 1;
        map.put(s.charAt(0),0);
        int res = 1;
        for(int i = 1;i < len;i++){
            if(!map.containsKey(s.charAt(i))){
                dp[i] = dp[i - 1] + 1;
            }else{
                int k = map.get(s.charAt(i));
                //i-k<=dp[i-1]说明在重复字符串范围内，需要更新长度
                //否则在范围外，可以使用dp[i-1]
                dp[i] = i - k <= dp[i - 1] ? i - k : dp[i - 1] + 1;
            }
            res = Math.max(res,dp[i]);
            map.put(s.charAt(i),i);
        }
        return res;
    }
}

    优化后

    空间复杂度O(1)

    class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() <= 0) return 0;
        int len = s.length();
        Map<Character,Integer> map = new HashMap<>();
        //优化=> 单个变量
        int dp = 1; 
        map.put(s.charAt(0),0);
        int res = 1;
        for(int i = 1;i < len;i++){
            if(!map.containsKey(s.charAt(i))){
                dp = dp + 1;
            }else{
                int k = map.get(s.charAt(i));
                //i-k<=dp[i-1]说明在重复字符串范围内，需要更新长度
                //否则在范围外，可以使用dp[i-1]
                dp = i - k <= dp ? i - k : dp + 1;
            }
            res = Math.max(res,dp);
            map.put(s.charAt(i),i);
        }
        return res;
    }
}class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() <= 0) return 0;
        int len = s.length();
        Map<Character,Integer> map = new HashMap<>();
        //优化=> 单个变量
        int dp = 1; 
        map.put(s.charAt(0),0);
        int res = 1;
        for(int i = 1;i < len;i++){
            if(!map.containsKey(s.charAt(i))){
                dp = dp + 1;
            }else{
                int k = map.get(s.charAt(i));
                //i-k<=dp[i-1]说明在重复字符串范围内，需要更新长度
                //否则在范围外，可以使用dp[i-1]
                dp = i - k <= dp ? i - k : dp + 1;
            }
            res = Math.max(res,dp);
            map.put(s.charAt(i),i);
        }
        return res;
    }
}
    0 赞同 0 条回复

# 回答此问题

后才能回答