哈希表
有效的字母异位词
这题基本上没什么太大难度,直接写就行了。
function isAnagram(s: string, t: string): boolean { if (s.length !== t.length) { return false } const record = new Map<string, number>() for (const ch of s) { record.set(ch, (record.get(ch) || 0) + 1) } for (const ch of t) { if (record.has(ch) && record.get(ch) > 0) { record.set(ch, record.get(ch) - 1) } else { return false } } return true }
两个数组的交集
这道题也是相对比较简单的,最后结果这里通过 Array.from(arr) 将哈希表转换为了数组。
function intersection(nums1: number[], nums2: number[]): number[] { const record = new Set<number>() for (const num of nums1) { record.add(num) } const res = new Set<number>() for (const num of nums2) { if (record.has(num)) { res.add(num) } } return Array.from(res) }
快乐数
题目中说了会无限循环,也就是说求和的过程中,sum 会重复出现。所以我们可以用一个哈希表来存储 sum,如果重复返回 false 就行了。
function isHappy(n: number): boolean { const record = new Set() while (true) { const sum = getSum(n) if (sum === 1) { return true } if (record.has(sum)) { return false } record.add(sum) n = sum } function getSum(n: number) { let sum = 0; while (n) { sum += (n % 10) * (n % 10) n = Math.floor(n / 10) } return sum } }
但是这道题其实还有其他的解法。现在我们的时间复杂度是 O(N),因为我们用了一个哈希表。其实这道题是可以在 O(1) 空间内求解的,用的是快慢指针的解法。快指针每次走两步,慢指针每次走一步,当二者相等时,即为一个循环周期。此时,判断是不是因为 1 引起的循环,是的话就是快乐数,否则不是快乐数。
function isHappy(n: number): boolean { let slow = n, fast = getSum(n) while (slow !== fast) { slow = getSum(slow) fast = getSum(getSum(fast)) } return slow === 1 function getSum(n: number) { let sum = 0; while (n) { sum += (n % 10) * (n % 10) n = Math.floor(n / 10) } return sum } }
两数之和
经典第一题,没什么好说的。
function twoSum(nums: number[], target: number): number[] { const record = new Map<number, number>() for (let i = 0; i < nums.length; i++) { const another = target - nums[i] if (record.has(another)) { return [i, record.get(another)] } record.set(nums[i], i) } }
四数相加 II
为什么这道题可以使用哈希表求解,但是三数之和和四数之和不行呢?这是因为这道题对应的是四个独立的数组,而三数之和和四数之和都是对于单个数组求解的。这一点必须要注意。
我们可以先求解 a + b 的结果,然后存储到数组中。注意这里 value 要存储计算结果的个数,因为这里对应着的是不同的解,都是要计算进去的。再用这个数组中的每一项来判断是否存在能够满足 a + b + c + d = 0 的解。
function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number { const record = new Map<number, number>() for (let i = 0; i < nums1.length; i++) { for (let j = 0; j < nums2.length; j++) { const sum = nums1[i] + nums2[j] record.set(sum, (record.get(sum) || 0) + 1) } } let res = 0 for (let i = 0; i < nums3.length; i++) { for (let j = 0; j < nums4.length; j++) { const sum = nums3[i] + nums4[j] if (record.has(-sum)) { res += record.get(-sum) } } } return res }
赎金信
这道题与有效的字母异位词一题解法基本完全相同,不多做解释。
function canConstruct(ransomNote: string, magazine: string): boolean { const record = new Map<string, number>() for (const ch of magazine) { record.set(ch, (record.get(ch) || 0) + 1) } for (const ch of ransomNote) { if (record.has(ch) && record.get(ch) > 0) { record.set(ch, record.get(ch) - 1) } else { return false } } return true }