[数据结构]字符串

练习1:

剑指 Offer 67. 把字符串转换成整数

var strToInt = function(str) {
    let matched = str.match(/^\s*(\-|\+)?\d+/g);
    if (!matched) return 0;
    let num = Number(matched[0].trimLeft())
    if (num > (2 ** 31 - 1)) return 2 ** 31 - 1
    if (num < -(2 ** 31)) return -(2 ** 31)
    return num;
};

3. 无重复字符的最长子串

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

给定字符串中最长无重复字符的子字符串 （同上）

双指针+哈希表
时间复杂度 O(n)
空间复杂度 O(∣Σ∣)

var lengthOfLongestSubstring = function(s) {
  // 滑动窗口+哈希表
  let left = -1;
  let maxLen = 0;
  let hashTable = new Map();
  for (let right=0; right < s.length; right++) {
      let cur = s.charAt(right);
      if (hashTable.has(cur) ) {
        left = Math.max(left, hashTable.get(cur));
      }
      hashTable.set(cur, right)
      maxLen = Math.max(maxLen, right - left)
  }
//   return s.slice(left+1, left+1+maxLen)
    return maxLen;
};

left、right分别指向最近两个相同字符的位置。
故需要求出截取出字符串， 使用s.slice(left+1, left+1+maxLen)
String.prototype.slice(start[, end])

https://leetcode-cn.com/leetbook/read/array-and-string/xkhi75/

https://leetcode-cn.com/tag/string/