3. 哈希表

242. 有效的字母异位词

242. 有效的字母异位词
0506，easy，quick
hash table

利用哈希表存储 s 字符串的所有字符：比如 a 在 s 中出现了 3 次，则最终结果为： key: 0, value: 3，b 的 key 为 2，以此类推。

在遍历 t 时，把字典表中的对应字母的个数相应的减去，最后可以得到结果。

要点：

- 'a' 的 ASCII 码为 97；
- 将一个字符转化为 ASCII 码：
    'a'.charCodeAt()   // 97

时间复杂度：O(m+n)，空间复杂度：O(1)。

var isAnagram = function (s, t) {
  // 'a'.charCodeAt() - '97'  --> 0
  const base = 97;
  const map = new Map();

  // 遍历s，依次登记字符出现次数
  for (const char of s) {
    const key = char.charCodeAt() - base;
    map.set(key, (map.get(key) || 0) + 1);
  }

  // 遍历s，依次减去出现的字符
  for (const char of t) {
    const key = char.charCodeAt() - base;
    if (!map.has(key)) return false;    // 如果不存在直接返回 false

    map.set(key, (map.get(key) || 0) - 1);
    if (map.get(key) === 0) map.delete(key); // 如果字符减少到0，则删除该字符
  }

  return map.size === 0 ? true : false
};

383. 赎金信

383. 赎金信
0506，easy，quick
hash table

和 242 上一题解法相同。

var canConstruct = function (ransomNote, magazine) {
  const map = new Map();

  for (const c of magazine) {
    map.set(c, (map.get(c) || 0) + 1);
  }

  for (const c of ransomNote) {
    if (!map.has(c)) return false;
    map.set(c, map.get(c) - 1);
    if (map.get(c) === 0) map.delete(c);
  }
  return true;
};

方法一：map 数组(不推荐)

maps 字典库：

每一种异位词都是一个独立的 map，key 为字母，value 为字母出现的次数。
多个 map 组成了一个 maps。

strs 遍历：

遇到一个词组时，先把它遍历为一个 curMap，然后在 maps 中查找是否有成员 map 和 curMap 相等：
- 如果相等，证明这不是一个新的异位词，则 curMap 丢弃不用，push 词组到 res 中对应位置。
- 如果不相等，证明这是一个新的异位词，则 curMap push 到 maps 中，词组 push 到 res 中。

var groupAnagrams = function (strs) {
  if (!strs.length) return [strs];

  // 一个数组，成员是多个map，每个map保存一种字母异位词
  // 一个零时map，用来检测正在的单词是否尚未登记在数组中。
  const maps = [];
  const res = [];

  for (const str of strs) {
    // 构造curMap
    const curMap = new Map();
    for (const char of str) {
      curMap.set(char, (curMap.get(char) || 0) + 1);
    }
    
    // 遍历maps，查看curMap是否已经在字典中。
    let flag = false;
    for (let i = 0; i < maps.length; i++) {
      // 和字典中的某个map相同
      if (equalMap(curMap, maps[i])) {
        res[i].push(str);
        flag = true;
        break;
      }
    }
    // 字典中没有curMap，curMap添加到字典中
    if (!flag) {
      maps.push(curMap);
      res.push([str]);
    }
  }
  return res;

  // 判断curMap 和 map 相同
  function equalMap(mapA, mapB) {
    // 注意，size 不相同肯定不是同一个map
    if (mapA.size ！== mapB.size) return false;
    for (const char of mapA.keys()) {
      if (mapA.get(char) !== mapB.get(char)) return false;
    }
    return true;
  }
};

方法二：map

不同的异位词，如果按照字母排序，其结果一定是相同的。所以不需要整理一个 maps（上一个方法），而是用一个 map 来存储所有的异位词，

key 是排好序的异位词，value 是属于该类别异位词的列表。

var groupAnagrams = function (strs) {
  const map = new Map();

  for (const str of strs) {
    const key = str.split('').sort().join('');    // 排序
    map.has(key) ? map.get(key).push(str) : map.set(key, [str]);
  }
  return Array.from(map.values());
};

时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的最大长度。
- 需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序（快排）以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklogk)。
空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

349. 两个数组的交集

349. 两个数组的交集
0506，easy，quick
哈希表 set

用一个 set 存储较短的数组成员

因为题干中要求如果出现相同字母且重复的情况，只输出一个，所以用 set 正好可以过滤掉重复的情况。

var intersection = function (nums1, nums2) {
  // 把较短的 nums 放入 set 中
  if (nums1 > nums2) [nums1, nums2] = [nums2, nums1];
  const set = new Set(nums1);
  const resSet = new Set();

  // for (const c of nums2) {
  //   set.has(c) && resSet.add(c);
  // }

  // for循环比迭代器效率更高
  for (let i = 0; i < nums2.length; i++) {
    set.has(nums2[i]) && resSet.add(nums2[i]);
  }
  return Array.from(resSet);
};

压缩一下代码：

var intersection = function (nums1, nums2) {
  return Array.from(new Set(nums1.filter(i => nums2.includes(i))))
};

// nums1.filter(i => nums2.includes(i))
// 这段代码的意思:
// filter 的返回值是一个数组，其cb 如果返回 true，则将 i 添加到数组中。

// nums1.filter(i => ..) 过滤 nums1 的成员，并返回需要的 i。
// nums2.includes(i)         判断 i 是否在 nums2 中。
// 如果nums1 的成员 i 也在 nums2 中，则会保留下来。

// 为什么要用 set 接住？因为如果返回的 i 可能有重复的，set 可以滤掉重复的成员。

350. 两个数组的交集 II

350. 两个数组的交集 II
0506，easy，quick
哈希表 map

用 Map 保存一个较短数组（如 nums1）的所有字母个数即可。

var intersect = function (nums1, nums2) {
  // 把较小的 nums 放入 map 中
  if (nums1 > nums2) [nums1, nums2] = [nums2, nums1];
  const map = new Map();
  const res = [];
  // 统计字典表
  for (let i = 0; i < nums1.length; i++) {
    map.set(nums1[i], (map.get(nums1[i]) || 0) + 1);
  }
  // 寻找
  for (let i = 0; i < nums2.length; i++) {
    if (map.has(nums2[i])) {
      map.set(nums2[i], map.get(nums2[i]) - 1);
      res.push(nums2[i]);
      // 如果减少到0，则删掉;
      if(map.get(nums2[i]) === 0)  map.delete(nums2[i]);
    }
  }
  return res;
};

复杂度分析

时间复杂度：O(m+n)；两个数组都要遍历一次；
空间复杂度：O(min(n, m))；只保存长度较小的数组；
哈希表操作复杂度：O(1)；

也可以用 Object 代替 Map

var intersect = function (nums1, nums2) {
  const data = {}
  const result = [];

  // 把较小的 nums 放入 data 中
  if (nums1 > nums2) [nums1, nums2] = [nums2, nums1];

  // 统计字典表
  for (let i = 0; i < nums1.length; i++) {
    if (data[nums1[i]]) data[nums1[i]]++
    else data[nums1[i]] = 1;
  }

  // 寻找
  for (let i = 0; i < nums2.length; i++) {
    if (data[nums2[i]]) {
      data[nums2[i]]--;
      result.push(nums2[i]);
    }
  }
  return result;
};

202. 快乐数

202. 快乐数
0507，easy，quick
哈希表 set

number 转化为 array，需要先转化为 string，然后再转化为 array：Array.from(n.toString())。

set：保存数字在转化过程中产生的值，每产生一个新值，就和 set 中进行对比，出现循环则返回 false。

var isHappy = function (n) {
  const set = new Set();

  while (true) {
    // n=1934  ==> "1934" ==> ['1','9','3','4']
    let arr = Array.from(n.toString());
    let res = 0;
    for (let i = 0; i < arr.length; i++) {
      res += arr[i] ** 2;
    }
    // 判断是否为1
    if (res === 1) return true;
    // 判断是否循环
    if (set.has(res)) return false;
    // 加入字典中
    set.add(res);
    // 下一轮循环
    n = res;
  }
};

1. 两数之和

1. 两数之和
0507，easy，quick
map 保存已扫描过的数字，方便之后用 O(1) 查看。

复杂度分析

时间复杂度：O(N)，其中 * 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。空间复杂度：O(N)，其中 N* 是数组中的元素数量。主要为哈希表的开销。

var twoSum = function (nums, target) {
  const map = new Map();

  // 遇到不符合条件，就放到map中
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) 
      return [map.get(target - nums[i]), i];
    else map.set(nums[i], i);
  }
};

454. 四数相加 II

454. 四数相加 II
0507，mid，answer
哈希表 + 2层 for 遍历

正常需要嵌套 4 层 for 循环，而这里转化成两个 2 层嵌套的 for 循环，时间复杂度：O(n^2)。

第一个 2 层 for 循环，把 nums1 和 nums2 遍历，统计可能出现的和，以及对应的次数，放入 map 中；
第二个 2 层 for 循环，把 nums3 和 nums4 遍历，每得出一个和，就拿它和 map 中的 key 做对比。
- nums1 + nums2 = - ( nums3 + nums4 )；

var fourSumCount = function (nums1, nums2, nums3, nums4) {
  let res = 0;
  const map = new Map();

  // 求 nums1 + nums2 可以组成的和，以及对应的次数：
  for (let i = 0; i < nums1.length; i++) {
    for (let j = 0; j < nums2.length; j++) {
      const count = nums1[i] + nums2[j];
      map.set(count, (map.get(count) || 0) + 1);
    }
  }

  // 求 count = - (nums3 + nums4)
  for (let i = 0; i < nums3.length; i++) {
    for (let j = 0; j < nums4.length; j++) {
      const count = nums3[i] + nums4[j];
      res += (map.get(0 - count) || 0);
    }
  }
  return res;
};

15. 三数之和

15. 三数之和
0507，mid，answer
双指针 + i 遍历

这道题有两个坑：

要求不能有重复的结果，所以不能用上一题的思路，a - b = -c 来判断，原因。更好的方法是使用双指针。
在双指针其实是 3 个指针，i 指针从头便利一遍 nums。然后在每个遍历周期，利用 left 和 right 去找结果。
- 在这找结果度时候，如果 i、left、right 遍历到了重复的值，就跳过这个值找下一个不同的值。
- 也可以在遍历中先不用去重，把符合的结果直接放到一个 set 中，然后返回 set。该思路太慢，就不列出了。

15.三数之和

时间复杂度：O(n^2)

var threeSum = function (nums) {
  if (nums.length < 3) return [];
  const res = [];
  nums.sort((x, y) => x - y);

  for (let i = 0; i < nums.length - 2; i++) {
    // 去重，当下一个值是重复的，就跳过
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let [left, right] = [i + 1, nums.length - 1];
    while (left < right) {
      let count = nums[i] + nums[left] + nums[right];
      if (count === 0) {
        // 找到符合条件的值，记录下来然后同时移动 left、right
        res.push([nums[i], nums[left], nums[right]]);
        left++;
        right--;
        // 去重，当下一个值是重复的，就跳过
        while (nums[left] === nums[left - 1]) left++;
        while (nums[right] === nums[right + 1]) right--;
      }
            else count < 0 ? left++ : right--;
    }
  }
  return res;
};

18. 四数之和

18. 四数之和
0507，mid，normal
双指针 + i, j 遍历

思路和三数之和相同，利用 i，j，left，right 四个指针完成遍历。

时间复杂度：O(n^3)

var fourSum = function (nums, target) {
  if (nums.length < 4) return [];
  const res = [];
  nums.sort((x, y) => x - y);
  console.log(nums);

  for (let i = 0; i < nums.length - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;// 去重 i
    for (let j = i + 1; j < nums.length - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue; // 去重 j

      let [left, right] = [j + 1, nums.length - 1];

      // 遍历 left、right
      while (left < right) {
        const count = nums[i] + nums[j] + nums[left] + nums[right];

        // 相等
        if (count === target) {
          res.push([nums[i], nums[j], nums[left], nums[right]]);
          left++, right--;
          // 去重 left、right 
          while (nums[left] === nums[left - 1]) left++;
          while (nums[right] === nums[right + 1]) right--;
        }

        // 不相等
        else count < target ? left++ : right--;
      }
    }
  }
  return res;
};

======= summary1 =============================================

Array、String、Map 的一些操作

// 字符串转化为数组
'abc'.split('');        //['a', 'b', 'c']
Array.from('abc');    //['a', 'b', 'c']


// 数组转化为字符串
['a', 'b', 'c'].toString();   //'a,b,c'
['a', 'b', 'c'].join('');           //'abc'


// 遍历 Map 的 value 并放入数组res中：
/*
    Map(3) {
    'aet' => [ 'eat', 'tea', 'ate' ],
    'ant' => [ 'tan', 'nat' ],
    'abt' => [ 'bat' ]
  }
*/
const res = [];
map.forEach(item => {
  res.push(item);
});
return res;

// 或者，
return Array.from(map.values());


// 迭代 / 遍历 map：
console.log(map.values());
console.log(map.keys());
console.log(map.entries());

// 会返回 map Iterator，迭代器可用于 Array.form() 的参数，不需要 forEach 自己往里凑了。
//[Map Iterator] { [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] }
//[Map Iterator] { 'aet', 'ant', 'abt' }
/*[Map Entries] {
    [ 'aet', [ 'eat', 'tea', 'ate' ] ],
    [ 'ant', [ 'tan', 'nat' ] ],
    [ 'abt', [ 'bat' ] ]
  }
*/

242. 有效的字母异位词​

383. 赎金信​

方法一：map 数组(不推荐)​

方法二：map​

349. 两个数组的交集​

350. 两个数组的交集 II​

202. 快乐数​

1. 两数之和​

454. 四数相加 II​

15. 三数之和​

18. 四数之和​