字符串 · HashMap · 栈

题干：找出数组中和为 target 的两个数的下标。

• 注意是返回下标，不能排序后双指针（排序会打乱下标）

var twoSum = function(nums, target) {
  let map = new Map() // val → index
  for (let i = 0; i < nums.length; i++) {
    let needNum = target - nums[i]
    if (map.has(needNum)) {
      return [map.get(needNum), i]
    }
    map.set(nums[i], i)
  }
}

题干：给定字符串，找出不含重复字符的最长子串长度。

// i,j 表示闭区间，闭区间内的字符都在 set 里
var lengthOfLongestSubstring = function(s) {
  if (s.length === 0) return 0
  let i = 0, j = 0
  let set = new Set()
  let maxLen = 0
  while (j < s.length) {
    if (!set.has(s[j])) {
      set.add(s[j])
      maxLen = Math.max(maxLen, j - i + 1)
      j++
    } else {
      // 从左边不断删，直到窗口内没有重复
      set.delete(s[i])
      i++
    }
  }
  return maxLen
}

题干：给定字符串 s，找出最长的回文子串。

• 分奇数基底（单个字符中心）和偶数基底（相邻两字符中心）两种情况扩散

var longestPalindrome = function (s) {
  let maxLen = 0, maxStr = ''

  // 奇数基底
  for (let i = 0; i < s.length; i++) {
    let l = i, r = i
    while (l - 1 >= 0 && r + 1 < s.length && s[l - 1] === s[r + 1]) {
      l--; r++
    }
    if (r - l + 1 > maxLen) { maxLen = r - l + 1; maxStr = s.slice(l, r + 1) }
  }

  // 偶数基底
  for (let i = 0; i < s.length; i++) {
    let l = i, r = i
    if (r < s.length - 1 && s[r + 1] === s[r]) r++
    while (l - 1 >= 0 && r + 1 < s.length && s[l - 1] === s[r + 1]) {
      l--; r++
    }
    if (r - l + 1 > maxLen) { maxLen = r - l + 1; maxStr = s.slice(l, r + 1) }
  }
  return maxStr
}

var longestCommonPrefix = function (strs) {
  let p = 0
  let minLen = Math.min(...strs.map(s => s.length))
  for (let i = 0; i < minLen; i++) {
    let curChar = strs[0][p]
    let flag = 0
    for (let j = 1; j < strs.length; j++) {
      if (strs[j][p] !== curChar) { flag = 1; break }
    }
    if (flag === 1) break
    else p++
  }
  return strs[0].slice(0, p)
}

题干：将字母异位词分组。如 ["eat","tea","ate"] 归一组。

• map.get(key) 拿到的是引用，可以直接 push

var groupAnagrams = function (strs) {
  let map = new Map()
  for (let i = 0; i < strs.length; i++) {
    let word = strs[i]
    let key = word.split('').sort().join() // 排序后作为 key
    if (!map.has(key)) map.set(key, [])
    map.get(key).push(word) // 直接 push 引用
  }
  let ans = []
  map.forEach((value) => ans.push(value))
  return ans
}

题干：给定未排序数组，找出最长连续元素序列的长度，要求 O(n)。

• 跳过思想：如果 set.has(val-1)，说明 val 不是序列起点，跳过
• 只从没有前驱的元素开始往后数

var longestConsecutive = function(nums) {
  let maxLen = 0
  let set = new Set(nums)
  set.forEach((val) => {
    if (!set.has(val - 1)) { // 没有前驱 → 是序列起点
      let curVal = val
      let curLen = 0
      while (set.has(curVal)) {
        curLen++
        curVal++
        maxLen = Math.max(maxLen, curLen)
      }
    }
  })
  return maxLen
}

题干：删除每个括号原语的最外层括号。

var removeOuterParentheses = function (s) {
  let ansStr = ''
  let count = 0
  let lastPos = 0
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') count++
    else count--
    if (count === 0) { // 原语结束
      ansStr += s.slice(lastPos + 1, i) // 去掉首尾
      lastPos = i + 1
    }
  }
  return ansStr
}

var removeDuplicates = function (s) {
  let stack = []
  for (let i = 0; i < s.length; i++) {
    let char = s[i]
    if (stack.length === 0 || stack[stack.length - 1] !== char) {
      stack.push(char)
    } else {
      stack.pop() // 相邻重复，消掉
    }
  }
  return stack.join('')
}