主要记录算法和数据结构学习笔记，新的一年更上一层楼！

初级算法-哈希表

• 一、有效的字母异位词
• 二、两个数组的交集
• 三、快乐数
• 四、两数之和
• 五、四数相加（二）
• 六、赎金信
• 七、三数之和
• 八、四数之和

哈希表

• 散列表有m个存储单元，散列函数H(key)=key%p，则p最好选为 小于等于m的最大素数
• 设有n个关键字具有相同hash函数值，用线性探索法把n个关键字映射到hash中，需要n*(n+1)/2次线性探测。

一、有效的字母异位词

1.题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

2.解题思路：

/*** @param {string} s* @param {string} t* @return {boolean}*/
var isAnagram = function(s, t) {if(s.length !== t.length) return false;const resSet = new Array(26).fill(0);const base = "a".charCodeAt();for(const i of s) {resSet[i.charCodeAt() - base]++;}for(const i of t) {if(!resSet[i.charCodeAt() - base]) return false;resSet[i.charCodeAt() - base]--;}return true;
};
// 运行时间：72ms
// 内存消耗：43MB

二、两个数组的交集

1.题目：
给定两个数组，编写一个函数来计算它们的交集。
说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

2.解题思路：

/*** @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersection = function(nums1, nums2) {// 根据数组大小交换操作的数组if(nums1.length < nums2.length) {const _ = nums1;nums1 = nums2;nums2 = _;}const nums1Set = new Set(nums1);const resSet = new Set();// for(const n of nums2) {//     nums1Set.has(n) && resSet.add(n);// }// 循环 比 迭代器快for(let i = nums2.length - 1; i >= 0; i--) {nums1Set.has(nums2[i]) && resSet.add(nums2[i]);}return Array.from(resSet);
};
// 运行时间：52ms
// 内存消耗：42.5MB

三、快乐数

1.题目：编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例1

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

2.解题思路：
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

var isHappy = function (n) {let m = new Map()const getSum = (num) => {let sum = 0while (n) {sum += (n % 10) ** 2n = Math.floor(n / 10)}return sum}while (true) {// n出现过，证明已陷入无限循环if (m.has(n)) return falseif (n === 1) return truem.set(n, 1)n = getSum(n)}
}// 运行时间：60ms
// 内存消耗：42.8MB

// 方法二：使用环形链表的思想 说明出现闭环 退出循环
var isHappy = function(n) {if (getN(n) == 1) return true;let a = getN(n), b = getN(getN(n));// 如果 a === b while (b !== 1 && getN(b) !== 1 && a !== b) {a = getN(a);b = getN(getN(b));}return b === 1 || getN(b) === 1 ;
};

// 方法三：使用Set()更简洁
/*** @param {number} n* @return {boolean}*/var getSum = function (n) {let sum = 0;while (n) {sum += (n % 10) ** 2;n =  Math.floor(n/10);}return sum;
}
var isHappy = function(n) {let set = new Set();   // Set() 里的数是惟一的// 如果在循环中某个值重复出现，说明此时陷入死循环，也就说明这个值不是快乐数while (n !== 1 && !set.has(n)) {set.add(n);n = getSum(n);}return n === 1;
};

// 方法四：使用Set()，求和用reduce
var isHappy = function(n) {let set = new Set();let totalCount;while(totalCount !== 1) {let arr = (''+(totalCount || n)).split('');totalCount = arr.reduce((total, num) => {return total + num * num}, 0)if (set.has(totalCount)) {return false;}set.add(totalCount);}return true;
};

四、两数之和

1.题目：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例1

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

2.解题思路：
遍历数组，哈希表不存在则加入map中，存在则返回下标和匹配key的下标。

var twoSum = function (nums, target) {let hash = {};for (let i = 0; i < nums.length; i++) {  // 遍历当前元素，并在map中寻找是否有匹配的keyif (hash[target - nums[i]] !== undefined) {return [i, hash[target - nums[i]]];}hash[nums[i]] = i;   // 如果没找到匹配对，就把访问过的元素和下标加入到map中}return [];
};
// 运行时间：80ms
// 内存消耗：41.6MB   

五、四数相加（二）

1.题目
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2²⁸ 到 2²⁸ - 1 之间，最终结果不会超过 2³¹ - 1 。
示例1

输入: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

2.解题思路：

/*** @param {number[]} nums1* @param {number[]} nums2* @param {number[]} nums3* @param {number[]} nums4* @return {number}*/
var fourSumCount = function(nums1, nums2, nums3, nums4) {const twoSumMap = new Map();let count = 0;// 统计nums1和nums2数组元素之和，和出现的次数，放到map中for(const n1 of nums1) {for(const n2 of nums2) {const sum = n1 + n2;twoSumMap.set(sum, (twoSumMap.get(sum) || 0) + 1)}}// 找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来for(const n3 of nums3) {for(const n4 of nums4) {const sum = n3 + n4;count += (twoSumMap.get(0 - sum) || 0)}}return count;
};
// 运行时间：172ms
// 内存消耗：44.6MB

六、赎金信

1.题目：
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：
你可以假设两个字符串均只含有小写字母。

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true
2.解题思路：

/*** @param {string} ransomNote* @param {string} magazine* @return {boolean}*/
var canConstruct = function(ransomNote, magazine) {const strArr = new Array(26).fill(0), base = "a".charCodeAt();for(const s of magazine) {  // 记录 magazine里各个字符出现次数strArr[s.charCodeAt() - base]++;}for(const s of ransomNote) { // 对应的字符个数做--操作const index = s.charCodeAt() - base;if(!strArr[index]) return false;  // 如果没记录过直接返回falsestrArr[index]--;}return true;
};
#运行时间：64ms
#内存消耗：44.1MB

七、三数之和

1.题目：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

var threeSum = function(nums) {const res = [], len = nums.length// 将数组排序nums.sort((a, b) => a - b)for (let i = 0; i < len; i++) {let l = i + 1, r = len - 1, iNum = nums[i]// 数组排过序，如果第一个数大于0直接返回resif (iNum > 0) return res// 去重if (iNum == nums[i - 1]) continuewhile(l < r) {let lNum = nums[l], rNum = nums[r], threeSum = iNum + lNum + rNum// 三数之和小于0，则左指针向右移动if (threeSum < 0) l++ else if (threeSum > 0) r--else {res.push([iNum, lNum, rNum])// 去重while(l < r && nums[l] == nums[l + 1]){l++}while(l < r && nums[r] == nums[r - 1]) {r--}l++r--}}}return res
};
#运行时间：172ms
#内存消耗：55.3MB

/***  nsum通用解法，支持2sum，3sum，4sum...等等*  时间复杂度分析：*  1. n = 2时，时间复杂度O(NlogN)，排序所消耗的时间。、*  2. n > 2时，时间复杂度为O(N^n-1)，即N的n-1次方，至少是2次方，此时可省略排序所消耗的时间。举例：3sum为O(n^2)，4sum为O(n^3)* @param {number[]} nums* @return {number[][]}*/
var threeSum = function (nums) {// nsum通用解法核心方法function nSumTarget(nums, n, start, target) {// 前提：nums要先排序好let res = [];if (n === 2) {res = towSumTarget(nums, start, target);} else {for (let i = start; i < nums.length; i++) {// 递归求(n - 1)sumlet subRes = nSumTarget(nums,n - 1,i + 1,target - nums[i]);for (let j = 0; j < subRes.length; j++) {res.push([nums[i], ...subRes[j]]);}// 跳过相同元素while (nums[i] === nums[i + 1]) i++;}}return res;}function towSumTarget(nums, start, target) {// 前提：nums要先排序好let res = [];let len = nums.length;let left = start;let right = len - 1;while (left < right) {let sum = nums[left] + nums[right];if (sum < target) {while (nums[left] === nums[left + 1]) left++;left++;} else if (sum > target) {while (nums[right] === nums[right - 1]) right--;right--;} else {// 相等res.push([nums[left], nums[right]]);// 跳过相同元素while (nums[left] === nums[left + 1]) left++;while (nums[right] === nums[right - 1]) right--;left++;right--;}}return res;}nums.sort((a, b) => a - b);// n = 3，此时求3sum之和return nSumTarget(nums, 3, 0, 0);
};
#运行时间：312ms
#内存消耗：59MB

八、四数之和

1.题目：
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

/*** @param {number[]} nums* @param {number} target* @return {number[][]}*/
var fourSum = function(nums, target) {const len = nums.length;if(len < 4) return [];nums.sort((a, b) => a - b);const res = [];for(let i = 0; i < len - 3; i++) {// 去重iif(i > 0 && nums[i] === nums[i - 1]) continue;for(let j = i + 1; j < len - 2; j++) {// 去重jif(j > i + 1 && nums[j] === nums[j - 1]) continue;let l = j + 1, r = len - 1;while(l < r) {const sum = nums[i] + nums[j] + nums[l] + nums[r];if(sum < target) { l++; continue}if(sum > target) { r--; continue}res.push([nums[i], nums[j], nums[l], nums[r]]);// 对nums[left]和nums[right]去重while(l < r && nums[l] === nums[++l]);while(l < r && nums[r] === nums[--r]);}} }return res;
};
#运行时间：88ms
#内存消耗：43.2MB