1. 两数之和
题目链接：https://leetcode-cn.com/problems/two-sum/
解题思路
1. 暴力求解
算法时间复杂度 O(n^2)
两层循环,外层循环枚举（或称作选中一个标杆）,内层循环从枚举值之后开始遍历,计算两数的和是否等于target。如果找到了两个数,那么返回这两个数的下标;
代码
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
};
function twoSum(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (target === nums[i] + nums[j]) {
return [i, j];
}
}
}
return [];
}
2. 哈希表求解
这道题最优的做法时间复杂度是 O(n)。
顺序遍历数组,对每?个元素a, 用target-nums[i]得到b, 若b存在于map中,直接返回 2 个数字的下标即可。如果b不存在, 就把a作为key, a的下标作为value存?map中,等待扫到“另?半”数字的时候,再取出来返回结果。
代码
var twoSum = function (nums, target) {
let map = new Map();
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i])) {
return [map.get(target - nums[i]), i];
}
map.set(nums[i], i);
}
return [];
};
function twoSum(nums: number[], target: number): number[] {
let map = new Map();
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i])) {
return [i, map.get(target - nums[i])];
}
map.set(nums[i], i);
}
return [];
}
202. 快乐数
题目链接：https://leetcode-cn.com/problems/happy-number/
解题思路
使用一个map存储计算过的数字，如果目前的数字已经计算过，表示死循环出现，return false。持续计算到 1 return true 或是死循环出现return false。
范例：判断 4 是不是 happy number
4 ^ 2 = 16
1 ^ 2 + 6 ^ 2 = 37
3 ^ 2 + 7 ^ 2 = 58
...
... = 20
2 ^ 2 + 0 = 4
4 重复出现，因此进入死循环
1. 哈希表
代码
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function (n) {
// map存储计算过的数字
let map = new Map();
// 如果nap里面出现过这个数字 或 数字 = 1，停止循环
while (!map.has(n) && n !== 1) {
map.set(n, n);
// 单纯的计算每一个位数的平方和
n.toString()
.split("")
.forEach((item, index) => {
if (index === 0) {
n = 0;
}
n += item * item;
});
n = parseInt(n);
}
return n === 1;
};
242.有效的字母异位词
题目链接：https://leetcode.cn/problems/valid-anagram/
解题思路
1. 转化为顺序字符串
代码
var isAnagram = function (s, t) {
return s.split("").sort().join("") == t.split("").sort().join("");
};
var isAnagram = function (s, t) {
return (
s.length == t.length && [...s].sort().join("") === [...t].sort().join("")
);
};
2.
定义一个数组叫做 record 用来上记录字符串 s 里字符出现的次数。
需要把字符映射到数组也就是哈希表的索引下表上，因为字符 a 到字符 z 的 ASCII 是 26 个连续的数值，所以字符 a 映射为下表 0，相应的字符 z 映射为下表 25。
再遍历 字符串 s 的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符 a 的 ASCII，只要求出一个相对数值就可以了。 这样就将字符串 s 中字符出现的次数，统计出来了。
那看一下如何检查字符串 t 中是否出现了这些字符，同样在遍历字符串 t 的时候，对 t 中出现的字符映射哈希表索引上的数值再做-1 的操作。
那么最后检查一下，record 数组如果有的元素不为零 0，说明字符串 s 和 t 一定是谁多了字符或者谁少了字符，return false。
最后如果 record 数组所有元素都为零 0，说明字符串 s 和 t 是字母异位词，return true。
代码
var isAnagram = function (s, t) {
if (s.length !== t.length) return false;
const record = new Array(26).fill(0);
const base = "a".charCodeAt();
for (const i of s) {
record[i.charCodeAt() - base]++;
}
for (const i of t) {
if (!record[i.charCodeAt() - base]) return false;
record[i.charCodeAt() - base]--;
}
return true;
};
349. 两个数组的交集
题目链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/
解题思路
1. 暴力解法
代码
var intersection = function (nums1, nums2) {
let len1 = nums1.length;
let len2 = nums2.length;
let set = new Set();
for (let i = 0; i < len1; i++) {
for (let j = 0; j < len2; j++) {
if (nums1[i] === nums2[j]) {
set.add(nums1[i]);
}
}
}
return Array.from(set);
};
2. 数组遍历
1）先判断nums1与nums2长度谁的长度短，遍历最短的数组
2）如果可以在长的数组nums1中找到nums2[i]，表示这是交集的数字
2）判断结果数组result是否已经有交集数字，如果没有就新增到结果数组resu1t中
时间复杂度为O(m*n)
代码
var intersection = function (nums1, nums2) {
let len1 = nums1.length;
let len2 = nums2.length;
let result = [];
if (len1 > len2) {
for (let i = 0; i < len2; i++) {
if (nums1.includes(nums2[i]) && !result.includes(nums2[i])) {
result.push(nums2[i]);
}
}
} else {
for (let i = 0; i < len1; i++) {
if (nums2.includes(nums1[i]) && !result.includes(nums1[i])) {
result.push(nums1[i]);
}
}
}
return result;
};
优化：
我们定义为nums2，如果nums1更短，使用解构赋值进行交换
代码
var intersection = function (nums1, nums2) {
let len1 = nums1.length;
let len2 = nums2.length;
let result = [];
[nums1, nums2] = len1 > len2 ? [nums1, nums2] : [nums2, nums1];
for (let i = 0; i < len2; i++) {
if (nums1.includes(nums2[i]) && !result.includes(nums2[i])) {
result.push(nums2[i]);
}
}
return result;
};
4. 使用 set
为了在线性时间内解决这个问题，我们使用集合set这一数据结构，该结构可以提供平均时间复杂度为O(1)
1）将两个数组都转换为集合，然后迭代较小的集合，检查其中的每个元素是否同样存在于较大的集合中
平均情况下，这种方法的时间复杂度为 O(n+m)
代码
var intersection = function (nums1, nums2) {
let set1 = new Set(nums1);
let set2 = new Set(nums2);
let result = new Set();
[set1, set2] = set1.size > set2.size ? [set1, set2] : [set2, set1];
for (let item of set2) {
if (set1.has(item) && !result.has(item)) {
result.add(item);
}
}
return Array.from(result);
};
5. 数组的 filter 方法
代码
var intersection = function (nums1, nums2) {
return Array.from(new Set(nums1.filter((x) => nums2.includes(x))));
};
6. 数组的 filter 方法+set 的 has 方法
代码
var intersection = function (nums1, nums2) {
let set2 = new Set(nums2);
return [...new Set(nums1.filter((x) => set2.has(x)))];
};
7. set
代码
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 (let i = nums2.length - 1; i >= 0; i--) {
nums1Set.has(nums2[i]) && resSet.add(nums2[i]);
}
return Array.from(resSet);
};
8. 双指针
代码
var intersection = function (nums1, nums2) {
nums1.sort((x, y) => x - y);
nums2.sort((x, y) => x - y);
const length1 = nums1.length,
length2 = nums2.length;
let index1 = 0,
index2 = 0;
const intersection = [];
while (index1 < length1 && index2 < length2) {
const num1 = nums1[index1],
num2 = nums2[index2];
if (num1 === num2) {
if (
!intersection.length ||
num1 !== intersection[intersection.length - 1]
) {
intersection.push(num1);
}
index1++;
index2++;
} else if (num1 < num2) {
index1++;
} else {
index2++;
}
}
return intersection;
};
|