共计 733 个字符，预计需要花费 2 分钟才能阅读完成。

Given a string, find the length of the longest substring withoutrepeating characters.
Example 1:
Input: “abcabcbb” Output: 3 Explanation: The answer is “abc”, withthe length of 3. Example 2:
Input: “bbbbb” Output: 1 Explanation: The answer is “b”, with thelength of 1. Example 3:
Input: “pwwkew” Output: 3 Explanation: The answer is “wke”, with thelength of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

对 xxx 串，它的最长不重复子串情况可以完全由 xx 可以决定，确认是 dp 问题确定状态转移方程，定义 dp[i] 为与当前串构成不重复串的 indexdp[i]=Math.max(dp[i-1],count[s.charAt(i-1)]+1);
public int lengthOfLongestSubstring(String s) {
int ret=0;
int l=s.length();
int[] dp=new int[l+1];
int[] count=new int[128];
for(int i=1;i<=l;i++){
dp[i]=Math.max(dp[i-1],count[s.charAt(i-1)]+1);
ret=Math.max(ret,i+1-dp[i]);
count[s.charAt(i-1)]=i;
}
return ret;
}

共计 1277 个字符，预计需要花费 4 分钟才能阅读完成。

原问题
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
我的沙雕解法
var lengthOfLongestSubstring = function(s) {
let recordObj = {};
let length = s.length;
let max = 0;
for(let i = 0; i < length; i++){
let record = 0;
for(let g = i; g < length; g++){
if(recordObj[s[g]] === undefined){// 无重复字母
recordObj[s[g]] = true;
record++;
}else{// 存在重复字母
recordObj = {};
break;
}
}
max = record > max? record:max;
if(max === length){break;}
}
return max;
};
挨打：最暴力的无脑解法，耗时 672ms。。。
贪心解法学习
参考了排名较前的答案，多数是贪心思想，以下摘抄一位的代码并加上学习的注释
/**
* 通过 i，j 指针计算子序列长度
* j 指针：表示当前循环的字母，i 指针：表示起点
* map 用于记录出现过的字母的相邻下标，给予 i 新的起点
* 重复字母出现时，比较当前起点与 map 的记录位置，取较大值，保证连续子序列，同时体现贪心：求
* 当前可求得的最长子序列
**/
var lengthOfLongestSubstring = function(s) {
var n = s.length, ans = 0;
var map = new Map(); // 记录出现过字母的相邻下标
// try to extend the range [i, j]
for (var j = 0, i = 0; j < n; j++) {
if (map.has(s.charAt(j))) {// 若此字母在之前的循环中出现过
i = Math.max(map.get(s.charAt(j)), i); // 保证连续子序列，同时体现贪心
}
ans = Math.max(ans, j – i + 1); // 比较
map.set(s.charAt(j), j + 1); // 记录字母的相邻位置
}
return ans;
};

此算法耗时 108ms 百度到一张图片很有利于理解 举例：qpxrjxkltzyx

图片来源：https://www.cnblogs.com/wangk…