其实从概念上讲集合应该是一个在Set、Map、Array之上的概念。至少在Java里面，集合的概念是Collection接口，直译不就是集合，而其实现分别有List、Set、Map。
但是这里的集合指的是：Set。不过避免歧义的话，后文就用Set英文来说事。
而Map这个概念，翻译成字典或者映射都可以，python里面就是Dictionary，其实和Map是一个东西。

概念

不管是Map或者Set，乃至Array或List。这类数据结构想做的事情就是收集，或者说存储数据。
只不过存储的方式不一样。

  • Array：数组使用连续的内存空间存储数据，对数据的重复性没有要求，存储有次序，而且逻辑上相邻的次序元素在物理上也相邻；
  • List：使用不连续的内存空间存储数据，对数据的重复性没有要求，也是有次序的，但是逻辑上相邻的元素，在物理上不相邻，其相邻关系是靠指针维持；
  • Set：对数据的重复性有要求，重复的数据只保持一份，没有次序的概念，物理存储上也不连续；
  • Map：与Set类似，只不过保存的从key到value的一对对元素（从key到value的映射），要求key不能重复，没有次序，不连续。

JS中的实现

Set与Map在ES6中都有实现。

ES6：Set

Set对象的基本增删改查：

  1. const set = new Set()
  3. // 增加元素
  4. set.add('a');
  6. // 删除元素
  7. set.delete('a')
  9. // 再次add这个元素
  10. // 还是只存这一份
  11. set.add('a');
  13. // 检查是否存在
  14. set.has('b') // return: fasle

ES6：Map

Map对象的基本增删改查：

  1. const map = new Map()
  3. // 增加元素
  4. map.set('name', 'ze');
  6. // 删除元素
  7. map.delete('name')
  9. // 再次set相同的key
  10. // 其value将会更新
  11. map.add('name', 'cjj');
  13. // 检查是否存在
  14. map.has('b') // return: fasle
  16. // 得到key对应的value
  17. map.get('name') // return 'cjj'

遍历

有这样的set和map：

  1. const set = new Set([1,2,3,4]);
  3. const map = new Map();
  4. map.set('name', 'yxnne');
  5. map.set('age', 31);

Set和Map可以使用同样的方法遍历：

  • for-of
  • forEach

用for-of遍历：

  1. // 遍历set
  2. for(s of set) {
  3.   console.log(s)
  4. }
  5. // 1
  6. // 2
  7. // 3
  8. // 4
  10. // 遍历map
  11. for(m of map) {
  12.   console.log(m)
  13. }
  14. // ["name", "yxnne"]
  15. // ["age", 31]
  17. // 直接解构
  18. for([k, v] of map) {
  19.   console.log(k, v)
  20. }

用forEach遍历：

  1. set.forEach((value, key) => {
  2.     console.log(value, key);
  3. })
  4. // 1 1
  5. // 2 2
  6. // 3 3
  7. // 4 4
  8. map.forEach((value, key) => {
  9.     console.log(value, key);
  10. })
  12. // yxnne name
  13. // 31 age

到这里发现，其实set和map特别像，虽然set在概念上并不是一个k-v的结构，但是JS实现的时候把set也视作和map一样的k-v键值对。只不过k和v是相等的。

面试题

Set、Map往往在编程题目中作为辅助技巧出现，这样，往往会简化很多问题：

数组利用Set去重

set构造函数的一个重载方法是将数组作为参数传入，生成一个set。再用展开运算把新的set生成一个数组就好：

  1. function noRepeatArray(arr) {
  2.     return [...new Set(arr)];
  3. }

LeetCode349：交集和差集

349. 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
说明：
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

可以利用set：

  1. var intersection = function(nums1, nums2) {
  2.     const noRepeatArr1 = [ ...new Set(nums1)];
  3.     const setArr2 = new Set(nums2);
  4.     return noRepeatArr1.filter(item => {
  5.         return setArr2.has(item);
  6.     })
  7. };

LeetCode1：两数之和

1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

分析下：
这个题虽然是第一题可是还真的没有那么easy，和第一题这种迷惑性题号太不相符。
需要考虑的点有：

  • 数组中有可能有重复的元素

比如：
[3,3]
6
这个用例期望[0, 1]

  • 另外，自身不能重复

比如：
[1,3,4,2]
6

如果重复的话就输出[1,1]了 但是期望是[2, 3]

这是之前一版本的答案：

  2. var twoSum = function (nums, target) {
  4.     // 记录下每一个元素的值和其下标
  5.     const valIndexMap = new Map();
  6.     nums.forEach((item, index) => {
  7.         const curIndexes = valIndexMap.get(item);
  8.         if (curIndexes) {
  9.             valIndexMap.set(item, [...curIndexes, index]);
  10.         } else {
  11.             valIndexMap.set(item, [index]);
  12.         }
  13.     });
  15.     // 遍历元素 
  16.     // 这里不能用forEach来return整个函数，别忘了
  17.     // nums.forEach((item, index) => {
  18.     //     const tofind = target - item;
  19.     //     const tofindIndex = valIndexMap.get(tofind);
  20.     //     console.log(tofindIndex)
  21.     //     if (tofindIndex) {
  22.     //         return [index, tofindIndex];
  23.     //     }
  24.     // });
  26.     // 使用for
  27.     for (let index = 0; index < nums.length; index += 1) {
  28.         const current = nums[index];
  29.         // valIndexMap.delete(current); // 这句话为什么 后面的注释在解释
  30.         const curIndexes = valIndexMap.get(current);
  31.         curIndexes.shift();
  32.         const tofind = target - current;
  33.         const tofindIndexArr = valIndexMap.get(tofind);
  34.         if (tofindIndexArr && tofindIndexArr.length > 0) {
  35.             return [index, tofindIndexArr.shift()];
  36.         }
  37.         // 这里还需要考虑另外一种情况
  38.         // 这个用例， 我们当前的情况会返回 1，1 也就是说，它重复考虑了3，index = 1 这个元素
  39.         // [1,3,4,2]
  40.         // 6
  41.         // 为了避免这样的事情，需要在没有匹配的时候删除
  42.     }
  44. };

之前的答案不太好，有更简便的答案
思路的转变在于，我们可以在map中记下值和下标
但是没有必要一开始就遍历一遍来专门记一次值和下标

  1. var twoSum = function (nums, target) {
  3.     // 用来记录下每一个元素的值和其下标
  4.     const valIndexMap = new Map();
  6.     for (let i = 0; i < nums.length; i += 1) {
  7.         const current = nums[i];
  8.         const toFind = target - current;
  9.         // if(valIndexMap.get(toFind)!== undefined){
  10.         if (valIndexMap.has(toFind)) {
  11.             return [valIndexMap.get(toFind), i]
  12.         } else {
  13.             // 如果没找到，这才放到map中，这些没找到里面总会有被拿走的
  14.             valIndexMap.set(current, i);
  15.         }
  16.     }
  18. };

LeetCode3：无重复字符的最长字串

3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

一般字串的问题，考虑双指针，维护一个窗口[left, right]
这个是一种不错的答案:

  1. var lengthOfLongestSubstring = function (s) {
  2.     // 构造双指针
  3.     let left = 0;
  4.     let res = 0;
  5.     const map = new Map();
  6.     for (let right = 0; right < s.length; right += 1) {
  7.         if (map.has(s[right]) && map.get(s[right]) >= left) { // 说明有重复
  8.             // 关键
  9.             left = map.get(s[right]) + 1;
  10.             console.log(left)
  11.         }
  12.         map.set(s[right], right);
  13.         res = Math.max(res, right - left + 1)
  15.     }
  16.     return res;
  17. };