最长不含重复字符的子字符串

题目思路

题目

给定一个字符串，找出其中不含有重复字符的最长子串的长度（来自LeetCood） 例如： 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路

使用动态规划 假设dp[j]表示以chars[j]字符为结尾的不含重复最长字串的长度。 s[i]表示chars[j]上一次出现的元素，即char[j]=s[i]。 那么对于dp[j]来说: 若d[j-1]<j-i，表示s[i]在d[j-1]得计算范围之外，则d[j] = d[j-1]+1。 若d[j-1]>=j-i，表示s[i]在d[j-1]得计算范围之内，则d[j] = j-i。 public static int lengthLongestOfSubstring(String s){ int dp = 0;//由于当前dp仅仅取决于前一个dp，所以可以用一个遍历来保存，节省O(n)空间 HashMap<Character, Integer> map = new HashMap<>();//用于存储chars[i]对应上一次出现得位置，默认为-1 int res = 0; for(int i=0; i<s.length(); i++){ map.put(s.charAt(i), i);//存储位置 dp = dp < i-map.getOrDefault(s.charAt(i), -1) ? dp+1 : i-map.get(s.charAt(i)); res = Math.max(res, dp); } return res; }

_{点击此处查看原LeetCode作者图文解析，更加清晰}