树

  • 与集合类似也是一种存储唯一的数据结构，但它以键值对的形式存储
  • Es6 有字典名为map

求交集

  1. let m = new Map();
  2. let nums1 = [1,2,3,2];
  3. let nums2 = [2,4,5,8,9,2,1];
  4. let res = [];
  6. nums1.forEach(num => {
  7.     m.set(num,true)
  8. });
  9. nums2.forEach(num => {
  10.     if(m.get(num)){
  11.         res.push(num);
  12.         m.delete(num)  
  13.     }
  14. })
  15. console.log(res)

有效括号算法优化

  2. const arr1 = [1,1,2,2];
  3. const set = new Set(arr1);
  4. const set2 = new Set([2,3]);
  5. const theSame = [...set].filter((item)=>{
  6.   set2.has(item)
  7. })
  8. const deferent = [...set].filter((item)=>{
  9.   !set2.has(item)
  10. })
  11. console.log('theSam1');
  12. console.log(theSame);
  13. console.log('deferent');
  14. console.log(deferent)

两数之和算法优化

给定 nums = [2,7,11,15] target = 9,因为nums[0] + nums[1] = 9,所以返回[0,1]

  1. let nums = [10,2,15,26];
  2. let target = 25;
  3. let numsAdd = function(numArray,target){
  4.    let map = new Map();
  5.    for(let i = 0;i<numArray.length;i++){
  6.      let n = numArray[i];
  7.      let n2 =target - n;
  8.      if(map.has(n2)){
  9.        return [map.get(n2),i]
  10.      }else{
  11.        map.set(n,i)
  12.      }   
  13.    }
  14.  };
  15.  console.log(numsAdd(nums,target))

无重复字符的最长子串(使用左右指针形成滑动窗口)

  2. let strings = ['a','c','b','a','d','e'];
  3. let getSubstringLength = function(string){
  4.   let leftIndex = 0;
  5.   let res = 0; //子字符串的长度
  6.   let map = new Map();
  7.   for(let rightIndex = 0;rightIndex<string.length;rightIndex++){
  8.     if(map.has(string[rightIndex])){
  9.       leftIndex = map.get(string[rightIndex])+1
  10.     };
  11.     res = Math.max(res,rightIndex - leftIndex + 1);
  12.     map.set(string[rightIndex],rightIndex);
  13.   }
  14.   return res
  15. }
  16. console.log(getSubstringLength(strings));