Longest Substring Without Repeating Characters —— leet code 每天一練
摘要：
滑動視窗
function lengthOfLongestSubstring(s: string) {
// const hashMap: { [key: string]: number } = {};
let max = 0;
let first ...
滑動視窗
function lengthOfLongestSubstring(s: string) {
// const hashMap: { [key: string]: number } = {};
let max = 0;
let first = "";
s.split('').forEach((value: string) => {
const indxe = first.indexOf(value);
if (indxe === -1) {
first += value;
} else {
max = first.length > max ? first.length : max;
first = first.substr(indxe + 1) + value;
}
});
max = first.length > max ? first.length : max;
return max;
}
執行情況:
Runtime: 88 ms, faster than 95.16% of JavaScript online submissions forLongest Substring Without Repeating Characters. Memory Usage: 40 MB, less than 66.18% of JavaScript online submissions forLongest Substring Without Repeating Characters.
上面的演算法利用了類似於滑動視窗的動作，獲取到相同字元的位置，然後得到該子字串。
複雜度分析：
-
時間複雜度: O(n + m) or O(n) = O(2n) in the worst case that each other character will be visited twice, ex: str = abcdefg.
-
空間複雜度：O(min(n, m)), 要麼就是目標字元 s 的長度，要麼就是子字串 fist 的長度。