每天一算法，脑子不生锈（真押韵）

示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true

// const s = '{[()]}'
const s = '()[]{}'
const arr = s.split('')
const obj = {
  "(": ")",
  "[": "]",
  "{": "}"
}
const stack = []
const valdate = data => {
  if (!data || data.length % 2 !== 0) return false
  let isRight = true
  data.split('').forEach(item => {
    if (obj[item]) {
      stack.push(item)
    } else {
      if (!stack.length || obj[stack.pop()] !== item) {
        isRight = false
      }
    }
  })
  if (stack.length) isRight = false
  return isRight
}
console.log(valdate(s)) // true

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
输入：nums = [3,2,4], target = 6
输出：[1,2]
输入：nums = [3,3], target = 6
输出：[0,1]

  const nums = [2, 7, 11, 15], target = 9;
  // const nums = [3, 2, 4], target = 6
  // const nums = [3, 3], target = 6
  // const twoSum = function(nums, target) {
  //   let i = 0
  //   let next
  //   let isFind = false
  //   while(i < nums.length - 1 && !next) {
  //     const current = nums[i]
  //     if (current >= 9) {
  //       i++
  //     } else {
  //       nums.forEach((item, index) => {
  //         if (i !== index && item + current === target) {
  //           next = index
  //         }
  //       })
  //       if (!next) i++
  //     }
  //   }
  //   if (next) {
  //     return [i, next]
  //   }
  // }
  // console.log(twoSum(nums, target))
  // 减少一层循环（时间复杂度）
  var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0, len = nums.length;i < len;i++) {
      if(map.has(target - nums[i])) {
          return [map.get(target - nums[i]), i];
      }
      map.set(nums[i], i);
    }
    return [];
  };
  console.log(twoSum(nums, target))

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
输入: s = ""
输出: 0

// 方便参考，输出连带字符串结果
const s = 'abcabcbb'
// const s = "bbbbb"
// const s = "pwwkew"
// const s = ''
const lengthOfLongestSubstring = (s) => {
  let str = ''
  let index = 0
  let obj = { len: index, str }
  if (!s) return obj
  s.split('').forEach(item => {
    if(str.includes(item)) {
      const { len } = obj
      if (index > len) obj = { len: index, str }
      index = 1
      str = item
    } else {
      str += item
      index++
    }
  })
  return obj
}
const { len, str } = lengthOfLongestSubstring(s)
console.log(len, str)

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
输入：nums = [0]
输出：[[],[0]]

const nums = [1, 2, 3]
// const subsets = nums => {
//   if (nums.length === 0) return [[]];
//   let resArr = [];
//   backtrack(nums, 0, [], resArr);
//   return resArr;
// };
// function backtrack(nums, index, subArr, resArr) {
//   if (Array.isArray(subArr)) {
//     resArr.push(subArr.slice());
//   }
//   if (index === nums.length) {
//     return;
//   } 
//   for (let i = index; i < nums.length; i++) {
//     subArr.push(nums[i]);
//     backtrack(nums, i + 1, subArr, resArr);
//     subArr.pop();
//   }
// }
// subsets(nums)
const getAllSubsets = nums => nums.reduce(
  (subsets, value) => subsets.concat(
    subsets.map(set => [value,...set])
  ),
[[]]);
console.log(getAllSubsets(nums));

输入：strs = ["flower","flow","flight"]
输出："fl"
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

// 如何减少遍历？这么搞打败不了对手啊
const strs = ["flower","flow","flight"]
// const strs = ["dog","racecar","car"]
// const strs = ["aab123v", 'aab123b', 'aba123a']
const longestCommonPrefix = strs => {
  strs.sort((a, b) => a.length - b.length)
  const [firtst, ...others] = strs
  let s = ''
  let isOver = false
  for(let i = 0; i < firtst.length; i++) {
    others.forEach(item => {
      if (item[i] !== firtst[i]) isOver = true
    })
    if (!isOver) {
      s += firtst[i]
    }
  }
  return s
};
longestCommonPrefix(strs)