从零学算法3

3.给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

• 我的思路，遍历字符串，用 hashMap 记录每个字符出现的索引，当出现重复字符时结算一次长度，然后将遍历索引更新到重复字符出现处，以它的后一位为新起点重新计算无重复子串长度。比如 “abcab”，当遍历到 i 为 3 时发现 a 之前有重复过，所以先结算当前长度 3，下一轮重新计算子串长度，并且从 a 后一位即 b 开始重新计算。

•   public int lengthOfLongestSubstring(String s) {Map<Character,Integer> map = new HashMap<>();int ans = 0;// 计算每一轮子串长度int temp = 0;for(int i=0;i<s.length();i++){char c = s.charAt(i);// 找到重复字符if(map.containsKey(c)){// 让下一轮遍历从最近重复字符下一位开始i = map.get(c);// 记得清空 map，不然直接就又重复了map.clear();// 结算长度ans = Math.max(ans,temp);// 长度归零temp=0;continue;}map.put(c,i);temp++;}ans = Math.max(ans,temp);return ans;}
  

• 他人解法1：实际上如果以动态规划的角度来看更加清晰明了，设 f(x) 为以字符串第 x 位结尾的最长无重复子串长度(以下简称答案好了)。当计算 f(j) 时，根据本题关键是否有重复字符，就划分成了两种情况，首先假设我当前正在计算长度的子串区间为 i~j，或者形象点 2~5，字符串为 ababcbcd，此时如果在我的区间即 abcb 内有和 x 处即位置 5 处的 b 重复的字符，比如位置 3 处的 b ，那么我这一轮的子串长度就为 5-3 也就是 cb 这一段的长度；否则就说明起码我这段区间没有重复字符，那我就可以在之前的基础上 + 1 了，即 dp[j-1]+1。比如 abcd，我从 a 开始往后找一直没有重复的字符，答案长度就一直累加。
• 总结一下就是对于 dp[j]，设有 s[j] 的最近重复字符 s[i]，如果 i 在 dp[j-1] 的区间外（没有重复字符也属于在区间外的情况），即 dp[j-1]<j-i（画两个线段就知道关系了，dp[j-1] 就是当前区间长度 x，j-i 就是重复字符到当前区间尾端的长度 y，y > x 就说明重复字符 i 在当前区间起点左侧，即不在当前区间），那 dp[j] = dp[j-1]+1；否则 dp[j] = j-i

•   i----------jx------j （dp[j-1]）
  

•   public int lengthOfLongestSubstring(String s) {Map<Character,Integer> map = new HashMap<>();int ans = 0;// temp 其实就是 dp[j-1]，不需要定义 dp 数组int temp = 0;for(int j=0;j<s.length();j++){char c = s.charAt(j);// 当前区间没有重复字符就返回 -1，// 因为 dp[j-1] < j 恒成立(因为你最长的情况下，一直没有重复字符长度也才 j-1)// 那 i 取负数的话 dp[j-1] < j-i 也是必定成立的int i = map.getOrDefault(c,-1);map.put(c,j);temp = temp < j-i?temp+1:j-i;ans=Math.max(temp,ans);}return ans;}
  

• 他人解法2：而其实不用 map 也可以，那就遍历寻找最近的重复字符，从当前遍历到的 s[j] 的前一位即 j-1 开始往前找重复字符。

•   public int lengthOfLongestSubstring(String s) {int ans = 0;// temp 其实就是 dp[j-1]，不需要定义 dp 数组int temp = 0;for(int j=0;j<s.length();j++){int i=j-1;// 这里也能把 i>=0 优化成 i >= j-temp// 因为不需要每次都找到s[0]，根据我们上面两条线段的分析// i 只要小于 x 了，就说明当前区间不包含重复字符了while(i>=0 && s.charAt(i) != s.charAt(j))i--;temp = temp < j-i?temp+1:j-i;ans=Math.max(temp,ans);}return ans;}
  

• 他人解法 3：在解法 1 的基础上来看，其实 temp + 1 可以看成当没有重复字符时，左端点 i 固定，j 随着遍历不断 + 1 后，j-i 也不断 +1；当发现重复字符时，更新 i 即可，然后答案依旧是取 j-i。

•   public int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>();// i：当前区间左端点int i = -1, ans = 0, len = s.length();for(int j = 0; j < len; j++) {// 为什么不是直接 map.get(s.charAt(j))？// 因为比如 "abba"，发现 b 重复时已经把 i 更新到 1// 然后再发现 a 时，其实那个 a 已经不在当前区间了// 也就是我们已经抛弃了前面的 ab，只计算 ba 的长度即可// 也就是只理会大于当前区间左端点的重复字符即可，所以要 maxif(map.containsKey(s.charAt(j)))i = Math.max(i, map.get(s.charAt(j)));map.put(s.charAt(j), j); ans = Math.max(ans, j-i); }return ans;}