共计 6002 个字符，预计需要花费 16 分钟才能阅读完成。
汇合与字典：
- 汇合常见的模式是 Set，字典常见的模式是 Map
- Set 和 Map 次要的利用场景在于 数据重组 和 数据贮存。
汇合 与 字典 的区别：
- 共同点：汇合、字典 能够贮存不反复的值
- 不同点：汇合相似于数组，元素的只有 key 没有 value，value 就是 key。字典是以 [key, value] 的模式贮存，键的范畴不限于字符串，各种类型的值（包含对象）都能够当作键
工夫复杂度：
set 或 map 能够用哈希表或均衡二叉搜寻树实现
哈希表实现的 map 或者 set 查找的工夫复杂度是O(1)，哈希表长处是查找十分快，哈希表的毛病是失去了数据的程序性，均衡二叉搜寻树实现的 map 或 set 查找时间复杂度是O(logn)，它保障了数据程序性
哈希函数
哈希函数是一个承受输出值的函数，由此输出计算出一个确定输入。
- 均匀分布：哈希函数计算出来的地址均匀分布
-
哈希碰撞：哈希函数计算出来的后果抵触
- 凋谢定址法
- 链地址法
447. 盘旋镖的数量 (medium)
给定立体上 n 对 互不雷同 的点 points，其中 points[i] = [xi, yi]。盘旋镖 是由点 (i, j, k) 示意的元组，其中 i 和 j 之间的间隔和 i 和 k 之间的欧式间隔相等（须要思考元组的程序）。
返回立体上所有盘旋镖的数量。
示例 1：
输出：points = [[0,0],[1,0],[2,0]]
输入：2
解释：两个盘旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
示例 2：输出：points = [[1,1],[2,2],[3,3]]
输入：2
示例 3：输出：points = [[1,1]]
输入：0提醒：
n == points.length
1 <= n <= 500
points[i].length == 2
-104 <= xi, yi <= 104
所有点都 互不雷同
- 思路：循环数组，找出与以后元素间隔雷同的点，记录频次退出 map 中，最初循环 map，从雷同间隔的数量中选取两个组合进去，退出后果中。从 m 个元素中选取两个的排列组合数 是
m*(m-1) - 复杂度：工夫复杂度
O(n^2)，数组遍历两层，空间复杂度O(n)，哈希表的空间
js：
//m = {1:3,2:5}
var numberOfBoomerangs = function (points) {
let ans = 0;
for (const p of points) {const m = new Map();
for (const q of points) {
// 统计间隔以后点雷同间隔的数量 退出 map 中
const dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
m.set(dis, (m.get(dis) || 0) + 1);
}
for (const [_, item] of m.entries()) {// 从雷同间隔的点的数量中选取两个
ans += item * (item - 1);
}
}
return ans;
};49. 字母异位词分组（medium）
给你一个字符串数组，请你将 字母异位词 组合在一起。能够按任意程序返回后果列表。
字母异位词 是由重新排列源单词的字母失去的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输出: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输入: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
示例 2:输出: strs = [“”]
输入: [[“”]]
示例 3:输出: strs = [“a”]
输入: [[“a”]]提醒：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅蕴含小写字母
办法 1. 排序
- 思路：遍历字符串数组，对每个字符串中的字符排序，退出 map 对应的 key 的数组中。
- 复杂度：工夫复杂度
O(n*klogk)，n 是字符串的个数，k 是最长的字符串的长度，排序复杂度O(klogk)，n 次排序，哈希表更新O(1)。空间复杂度O(nk)，排序空间复杂度O(nlogk)，map 空间复杂度O(nk)，取较大的O(nk)
js：
var groupAnagrams = function(strs) {const map = new Map();
for (let str of strs) {let array = Array.from(str);// 字符转成数组
array.sort();// 排序
let key = array.toString();
let list = map.get(key) ? map.get(key) : new Array();// 从 map 中取到相应的数组
list.push(str);// 退出数组
map.set(key, list);// 从新设置该字符的数组
}
return Array.from(map.values());//map 中的 value 转成数组
};办法 2. 计数
- 思路：题意是字符串的字符都是小写，能够对每个字符串统计其中字符的频次，将每个字符频次雷同的字符串放在一组
- 复杂度：工夫复杂度
O(n*k)，n 是字符串个数，k 是最长字符串长度，循环字符串数组复杂度O(n)，对每个字符串统计频次复杂度O(k)。空间复杂度O(n*k)，map 中寄存了 n 个大小最长为 k 的字符串。
js：
var groupAnagrams = function(strs) {const map = {};
for (let s of strs) {// 循环字符串数组
const count = new Array(26).fill(0);// 字符都是小写，初始化大小为 26 的数组
for (let c of s) {// 对字符串的每个字符统计频次
count[c.charCodeAt() - 'a'.charCodeAt()]++;
}
map[count] ? map[count].push(s) : map[count] = [s];// 退出 map
}
return Object.values(map);
};242. 无效的字母异位词 (easy)
给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。
留神：若 s 和 t 中每个字符呈现的次数都雷同，则称 s 和 t 互为字母异位词。
示例 1:
输出: s = “anagram”, t = “nagaram”
输入: true
示例 2:输出: s = “rat”, t = “car”
输入: false提醒:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅蕴含小写字母进阶: 如果输出字符串蕴含 unicode 字符怎么办？你是否调整你的解法来应答这种状况？
办法 1. 排序
- 思路：两个字符串转成数组，排序后转回字符串进行比拟。
- 复杂度剖析：工夫复杂度
O(nlogn)，排序采纳快排，工夫复杂度是 nlogn，比拟两字符串是否相等工夫复杂度为 n，O(n)+O(nlogn)=O(nlogn)。空间复杂度为O(logn)，排序须要O(logn)的空间，java 和 js 字符串是不可变的，须要额定的O(n)空间来拷贝字符串，咱们疏忽这个复杂度，这依赖不同语言实现的细节。
办法 2. 哈希表:
- 思路：采纳空间换工夫的策略，筹备一个数组，循环字符串 s，每个元素呈现一次加 1，而后循环 t 元素，每次呈现的字符减 1，如果 t 中呈现一些不在 s 中的字符 则返回 false，所有循环完结 阐明两个字符串中每个字符的数量雷同
- 复杂度剖析：工夫复杂度
O(n),n 是字符串的长度，空间复杂度O(s)，s 为字符集大小
js:
var isAnagram = function(s, t) {if (s.length !== t.length) {// 长度不想等 间接返回 false
return false;
}
const table = new Array(26).fill(0);// 大小为 26 的数组
for (let i = 0; i < s.length; ++i) {// 循环字符串 s，每个元素呈现一次加 1
table[s.codePointAt(i) - 'a'.codePointAt(0)]++;
}
for (let i = 0; i < t.length; ++i) {// 循环 t 元素
table[t.codePointAt(i) - 'a'.codePointAt(0)]--;// 每次呈现的字符减 1
// 如果 t 中呈现一些字符对于 s 中的字符 则返回 false
if (table[t.codePointAt(i) - 'a'.codePointAt(0)] < 0) {return false;}
}
return true;// 所有循环完结 阐明两个字符串中每个字符的数量雷同
}187. 反复的 DNA 序列 (medium)
DNA 序列 由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。
例如，”ACGAATTCCG” 是一个 DNA 序列。
在钻研 DNA 时，辨认 DNA 中的反复序列十分有用。给定一个示意 DNA 序列 的字符串 s，返回所有在 DNA 分子中呈现不止一次的 长度为 10 的序列(子字符串)。你能够按 任意程序 返回答案。
示例 1：
输出：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输入：[“AAAAACCCCC”,”CCCCCAAAAA”]
示例 2：输出：s = “AAAAAAAAAAAAA”
输入：[“AAAAAAAAAA”]提醒：
0 <= s.length <= 105
s[i]==’A’、’C’、’G’ or ‘T’
- 思路：用 map 存储子串呈现的次数，循环 dna 序列，每次截取长度为 10 的子串，退出 map 中 并更新呈现的次数，次数超过 2，退出 ans
- 复杂度：工夫复杂度
O(n)，n 是字符串的长度。空间复杂度O(n)
js：
var findRepeatedDnaSequences = function(s) {
const L = 10;
const ans = [];
const cnt = new Map();
const n = s.length;
for (let i = 0; i <= n - L; ++i) {const sub = s.slice(i, i + L)// 截取长度为 10 的子串
cnt.set(sub, (cnt.get(sub) || 0) + 1);// 退出 map 中 并更新呈现的次数
if (cnt.get(sub) === 2) {ans.push(sub);
}
}
return ans;
};454. 四数相加 II（medium）
给你四个整数数组 nums1、nums2、nums3 和 nums4，数组长度都是 n，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0示例 1：
输出：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输入：2
解释：
两个元组如下：
- (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：输出：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输入：1提醒：
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
办法 1: 哈希表
- 思路：在 A 和 B 中取出两个数的组合，将这两个数的和作为键，呈现次数作为值退出哈希表中，循环 C、D，判断 C 和 D 中是否存在两个数的和 加 AB 中的俩元素的和正好是 0，统计组合数
- 复杂度：工夫复杂度
O(n^2), 两个嵌套循环。空间复杂度O(n^2)，哈希表的空间，最差的状况下是n^2
js：
var fourSumCount = function(A, B, C, D) {const countAB = new Map();
// 在 A 和 B 中取出两个数的组合，将这两个数的和作为键，呈现次数作为值退出哈希表中，A.forEach(u => B.forEach(v => countAB.set(u + v, (countAB.get(u + v) || 0) + 1)));
let ans = 0;
for (let u of C) {// 循环 C、D
for (let v of D) {if (countAB.has(-u - v)) {// 判断 C 和 D 中是否存在两个数的和 加 AB 中的俩元素的和正好是 0
ans += countAB.get(-u - v);// 累加组合数
}
}
}
return ans;
};1. 两数之和 (easy)
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你能够假如每种输出只会对应一个答案。然而，数组中同一个元素在答案里不能反复呈现。
你能够按任意程序返回答案。
示例 1：
输出：nums = [2,7,11,15], target = 9
输入：[0,1]
解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。
示例 2：输出：nums = [3,2,4], target = 6
输入：[1,2]
示例 3：输出：nums = [3,3], target = 6
输入：[0,1]提醒：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个无效答案
进阶：你能够想出一个工夫复杂度小于 O(n2) 的算法吗？
办法 1. 暴力枚举
- 思路：两层 for 循环，第一层
for i:0->n-1, 枚举 nums 中的每一个数 x，第二层for j：i+1->n-1，寻找是否存在两个数字的和是 target。 - 复杂度剖析：工夫复杂度：
O(n^2), n 为数组的长度。空间复杂度O(1)。
办法 2. 哈希表：
动画过大，点击查看
- 思路：办法一第一层循环是必须的，要害是优化第二次循环，也就是寻找
targrt-x的过程，这里要害采纳空间换工夫，也就是采纳哈希表进行优化，让查找的过程变为O(1)。首先还是遍历 nums 数组，而后在哈希表中寻找target-x，如果不存在就把以后元素 x 和下标存入哈希表，如果存在就返回target-x和以后元素的下标 - 复杂度剖析：工夫复杂度
O(n)，n 为数组的长度，空间复杂度O(n)，n 为数组的长度，次要是哈希表的空间开销
js:
var twoSum = function (nums, target) {const map = new Map();
for (let i = 0; i < nums.length; i++) {// 第一层循环
const complement = target - nums[i];
if (map.has(complement)) {// 判断 complement 是否在 map 中
return [map.get(complement), i]; // 存在的话返回两个数的下标
} else {map.set(nums[i], i);// 不存在 map 中就将以后元素和下标存入 map
}
}
return [];};视频解说：传送门