剑指 Offer 48. 最长不含重复字符的子字符串

image.png
image.png

图片转自 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dz9di/

动态规划 + 哈希表

  1. public class Solution {
  3.     public int lengthOfLongestSubstring(String s) {
  4.         // 临时变量存储本次循环得到的子串长度
  5.         int temp = 0;
  6.         // 记录 temp 的最大值，返回此值
  7.         int res = 0;
  8.         // 字符串长度
  9.         int len = s.length();
  10.         // 用于存放字符与索引的对应关系，快速得到子串中是否存在此字符
  11.         HashMap<Character, Integer> map = new HashMap<>();
  13.         for (int i = 0; i < len; i++) {
  14.             // 先获取当前字符是否在子串中，如果不存在返回 -1
  15.             int j = map.getOrDefault(s.charAt(i), -1);
  17.             // 上一步获取完之后再更新到 map 中
  18.             map.put(s.charAt(i), i);
  20.             // 计算子串长度，这一步是关键
  21.             // 如果 temp 比 i - j 小说明子串没有出现重复的情况，所以 temp 等于自身累加 1
  22.             // 反之说明出现重复了，所以 temp 等于 (当前索引 - 该字符的上一次出现的索引)
  23.             temp = temp < i - j ? temp + 1 : i - j;
  25.             // 记录最大值
  26.             res = Math.max(res, temp);
  27.         }
  28.         return res;
  29.     }
  30. }

动态规划 + 哈希表，左索引定义跟上个方法不一样

public class Solution {

    public int lengthOfLongestSubstring(String s) {
        // 存放字符 s[i] 上一次出现的位置，如果没有出现过实例值为 - 1
        // 所以子串长度等于 i - pre
        int pre = -1;
        // 记录最大值，返回此值
        int res = 0;
        // 字符串长度
        int len = s.length();
        // 用于存放字符与索引的对应关系，快速得到子串中是否存在此字符
        HashMap<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < len; i++) {
            // 先获取再更新
            // 获取左索引
            if (map.containsKey(s.charAt(i))) {
                // 获取较大值，左索引不能往回退
                pre = Math.max(map.get(s.charAt(i)), pre);
            }
            // 更新当前字符索引
            map.put(s.charAt(i), i);
            // 记录最大值
            res = Math.max(res, i - pre);
        }
        return res;
    }
}