一、集合（无序且唯一）
1、常用操作
- 使用Set对象： new、add、delete、has、size
- 迭代Set: 多种迭代方法、Set与Array互转、求交集/差集
let mySet = new Set();
// 添加
mySet.add(1);
mySet.add(5);
mySet.add(5);
// 1 ,5
mySet.add('some text')
let o = {a: 1, b: 2};
mySet.add(o);
mySet.add({a: 1, b: 2});
// 判断是否包含
const has = mySet.has(3) // false
mySet.delete(5)
// 迭代
for(let item of mySet) console.log(item)
for(let item of mySet.keys()) console.log(item)
for(let item of mySet.values()) console.log(item)
for(let [ key, value] of mySet.entries()) console.log(key, value)
// Set与Array互转
const myArr = [...mySet];
const myArr = Array.from(mySet);
const mySet2 = new Set([1,2,3,4]);
// 求交集和差集
// 交集
const intersection = new Set([...mySet].filter(x => mySet2.has(x) ))
// 先变成数组，再筛选set2中的值
// 差集
const diffetence = new Set([...mySet].filter(x => !mySet2.has(x) ))
// 去重
const arr = [1, 1, 3, 3]
const arr2 = [...new Set(arr)]
二、字典(键值对，Map)
1、字典的常用操作
const m = new Map();
// 增加
m.set('a', 'aa');
// 查
m.get('a');
// 删
m.delete('b');
m.clear(); // 删除所有元素
// 改（set会覆盖）
m.set('a', 'aaa');
20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
输入：s = "()"
输出：true
var isValid = function(s) {
if(s.length % 2 === 1) return false;
const stack = [];
const map = new Map();
map.set('(', ')');
map.set('{', '}');
map.set('[', ']');
for(let i = 0; i < s.length; i += 1) {
const c = s[i];
if(map.has(c)){
stack.push(c)
} else {
const t = stack[stack.length -1];
if(map.get(t) === c) {
stack.pop()
} else{
return false
}
}
}
return stack.length === 0;
}
1. 两数之和 - 力扣（LeetCode） (leetcode-cn.com)
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
var twoSum = function(nums, target) {
const map = new Map();
for(let i = 0; i < nums.length; i += 1) {
const n = nums[i];
const n2 = target - n;
if(map.has(n2)) {
return [map.get(n2), i]
} else {
map.set(n, i)
}
}
};
3. 无重复字符的最长子串 - 力扣（LeetCode） (leetcode-cn.com)
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
滑动窗口 + 查找表
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let l = 0; // 左指针为0
let res = 0; // 最大窗口的长度
const map = new Map();
for(let r = 0; r < s.length; r ++) { // 右指针
if(map.has(s[r]) && map.get(s[r]) >= l) {
l = map.get(s[r]) + 1
}
res = Math.max(res, r - l + 1); // 窗口长度的最大值
map.set(s[r], r)
}
return res;
};
76. 最小覆盖子串 - 力扣（LeetCode） (leetcode-cn.com)
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
滑动窗口+查找表
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
let l = 0;
let r = 0;
const need = new Map();
for(let c of t) {
need.set(c, need.has(c) ? need.get(c) + 1: 1);
}
let needType = need.size;
let res = '';
while( r < s.length) {
const c = s[r]
if(need.has(c)) {
need.set(c, need,get(c) - 1);
if(need.get(c) === 0) needType -= 1
}
while(needType === 0) {
console.log(s.substring(l, r + 1));
const c2 = s[l];
if(need.has(c2)) {
need.set(c2, need.get(c2) + 1);
if(need.get(c2) === 1) needType += 1
}
l += 1;
}
r += 1
}
return res
}
349. 两个数组的交集 - 力扣（LeetCode） (leetcode-cn.com)
给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
Map
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2){
const map = new Map();
nums1.forEach(n => {
map.set(n, true)
})
const res = []
nums2.forEach(n => {
if(map.get(n)){
res.push(n)
map.delete(n)
}
})
return res
}
// 第2种
var intersection = function(nums1, nums2) {
return [...[...new Set(nums1)].filter(n => new Set(nums2).has(n))]
}
// 第3种
var intersection = function(nums1, nums2) {
return [...[...new Set(nums1)].filter(n => nums2.includes(n))]
};
Set
var intersection = function(nums1, nums2) {
let setArray = new Set()
for(let i = 0; i < nums1.length; i++) {
setArray.add(nums1[i])
}
let setResult = new Set()
for(let i = 0; i < nums2.length; i++) {
if(setArray.has(nums2[i])){
setResult.add(nums2[i])
}
}
return Array.from(setResult)
}
350. 两个数组的交集 II - 力扣（LeetCode） (leetcode-cn.com)
给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
if (nums1.length === 0 || nums2.length === 0) { return []}
let map = new Map()
for (let i = 0; i < nums1.length; i++) {
if (map.has(nums1[i])){
map.set(nums1[i], map.get(nums1[i])+1)
}else {
map.set(nums1[i], 1)
}
}
let arr = []
for (let i = 0; i < nums2.length; i++){
if (map.has(nums2[i]) && map.get(nums2[i]) != 0){
arr.push(nums2[i])
map.set(nums2[i], map.get(nums2[i])-1)
}
}
return arr;
};
242. 有效的字母异位词 - 力扣（LeetCode） (leetcode-cn.com)
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
输入: s = "anagram", t = "nagaram"
输出: true
var isAnagram = function(s, t) {
if(s.length !== t.length) {
return false
}
const map = new Map()
s.split('').forEach(sItem => {
map.set(sItem, map.has(sItem) ? map.get(sItem) + 1 : 1)
})
t.split('').forEach(tItem => {
if(map.has(tItem)) {
map.set(tItem, map.get(tItem) - 1)
} else {
return false
}
})
return [...map.values()].every(item => item === 0)
};
202. 快乐数 - 力扣（LeetCode） (leetcode-cn.com)
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = sum =>{
const ARRAY = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
const ZERO = '0'.charCodeAt(0) // ZERO 为48
let hasSeen = new Set()
while(true){
if(sum === 1) return true
if (hasSeen.has(sum)){
return false
}
hasSeen.add(sum)
let str = sum.toString()
sum = 0
for (let i=0; i<str.length; i++){
sum += ARRAY[str.charCodeAt(i) - ZERO]
}
}
}
290. 单词规律 - 力扣（LeetCode） (leetcode-cn.com)
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
/**
* @param {string} pattern
* @param {string} s
* @return {boolean}
*/
var wordPattern = function(pattern, s) {
var arr = s.split(' ');
if(pattern.length != arr.length) return false;
for(let i=0; i< pattern.length; i++){
// indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置
if(pattern.indexOf(pattern[i]) != arr.indexOf(arr[i])){
return false
}
}
return true
};
205. 同构字符串 - 力扣（LeetCode） (leetcode-cn.com)
给定两个字符串 s 和 t，判断它们是否是同构的。
输入：s = "egg", t = "add"
输出：true
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isIsomorphic = function(s, t) {
let hash1 = new Map()
let hash2 = new Map()
for(let i=0; i<s.length; i++){
let S = s[i]
let T = t[i]
if(hash1.has(S)){
if(hash1.get(S) !== T) return false
} else if(hash2.has(T)) {
if(hash2.get(T) !== S) return false
} else {
hash1.set(S, T)
hash2.set(T,S)
}
}
return true
};
451. 根据字符出现频率排序 - 力扣（LeetCode） (leetcode-cn.com)
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
输入:"tree"
输出:"eert"
/**
* @param {string} s
* @return {string}
*/
var frequencySort = function(s) {
const map = new Map()
s.split('').forEach(item => {
map.set(item, map.has(item) ? map.get(item) + 1: 1)
})
let array = [...map].sort((arr1, arr2) => arr2[1] - arr1[1])
return array.map(item => item[0].repeat(item[1])).join("")
};
1. 两数之和 - 力扣（LeetCode） (leetcode-cn.com)
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map();
for(let i = 0; i < nums.length; i += 1) {
const n = nums[i];
const n2 = target - n;
if(map.has(n2)) {
return [map.get(n2), i]
} else {
map.set(n, i)
}
}
};
15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
// 从小到大排序
nums = nums.sort((a, b) => a - b)
let result = []
for (let i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break; // 最小数字如果大于0，则后面不会有和为0的组
if (nums[i] === nums[i - 1]) continue; // 跳过相同的数字
// 其中，nums[i]是最小的数字，nums[k]是最大的数字
let j = i + 1
let k = nums.length - 1
// 第二个数的索引不能超过第三个数的索引
while (j < k) {
let sum = nums[i] + nums[j] + nums[k]
if (sum > 0) {
// 如果结果大于0，那么最大的数字索引减一，寻找更小的数字
do {k--} while (nums[k] === nums[k + 1]) // 跳过相同的数字
} else {
// 如果结果等于0，加入数组
if (!sum) result.push([nums[i], nums[j], nums[k]])
// 如果结果不大于0，那么次大的数字索引加一，寻找更大的数字
do {j++} while (nums[j] === nums[j - 1]) // 跳过相同的数字
}
}
}
return result
};
18. 四数之和 - 力扣（LeetCode） (leetcode-cn.com) 【不理解】
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
思路：回溯剪枝
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
const result = [];
nums.sort((a, b) => a-b); // 排序
const set = new Set(); // 去重
// 回溯，path 路径 sum 路径和 index 数组索引
const recursion = (path, sum, index) => {
for(let i = index; i < nums.length; i++) {
// 设置下一次遍历的和
const nextSum = sum + nums[i];
// 路径和大于目标和，终止
if(nextSum > 0 && nextSum > target) {
break;
}
// 路径path添加当前元素
path.push(nums[i])
// 路径长度到4
if(path.length === 4) {
if(nextSum === target) {
const pathStr = path.join('-')
if(!set.has(pathStr)) {
result.push(path.slice())
set.add(pathStr)
}
}
}else {
recursion(path, nextSum, i+ 1)
}
path.pop()
}
}
recursion([], 0, 0)
return result
};
16. 最接近的三数之和 - 力扣（LeetCode） (leetcode-cn.com)
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
双指针
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
nums.sort((a,b) => a-b)
let res = nums[0] + nums[1] + nums[2]
let len = nums.length;
for(let i = 0; i < len; i++){
let left = i+1, right = len -1
while(left < right) {
let sum = nums[i] + nums[left] + nums[right]
if(Math.abs(sum - target) < Math.abs(res - target)) {
res = sum
}
if(sum < target){
left ++
} else if(sum > target) {
right--;
} else {
return res
}
}
}
return res
};
454. 四数相加 II - 力扣（LeetCode） (leetcode-cn.com)
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:2
解释:
(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number[]} nums3
* @param {number[]} nums4
* @return {number}
*/
var fourSumCount = function(nums1, nums2, nums3, nums4) {
// 查找表
let map = new Map()
// 遍历A和B
nums1.forEach(item1 => {
nums2.forEach(item2 => {
// nums1和nums2的和出现的次数存在map中
const sum = item1 + item2
map.has(sum) ? map.set(sum, map.get(sum) + 1) : map.set(sum, 1)
})
})
let count = 0
nums3.forEach(item3 => {
nums4.forEach(item4 => {
const sum = item3 + item4
if(map.has(-sum)) {
count += map.get(-sum)
}
})
})
return count
};
