454. 四数相加 II
这个第一时间没想出来怎么做的;
后面看了题解才发现可以两两分组;绝了
/**
* @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()
let count = 0
for(let i = 0; i< nums1.length; i++){
for(let j = 0; j<nums2.length;j++){
if(map.has(nums1[i]+nums2[j])){
map.set(nums1[i]+nums2[j],map.get(nums1[i]+nums2[j])+1)
}else{
map.set(nums1[i]+nums2[j],1)
}
}
}
for(let i = 0; i< nums3.length; i++){
for(let j = 0; j<nums4.length;j++){
if(map.has(-(nums3[i]+nums4[j]))){
count+=map.get(-(nums3[i]+nums4[j]))
}
}
}
return count
};
383. 赎金信
确实和有效的字母异位词很像, 第一时间还想用滑动窗口, 但发现不要求连续,可能这也是题目名的奥妙
/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
//注意和寻找子串异构词不同的是, 这里不要求连续
var canConstruct = function(ransomNote, magazine) {
if(ransomNote.length>magazine.length){
return false
}
let map = new Map()
for(let i = 0;i<ransomNote.length;i++){
if(!map.has(ransomNote[i])){
map.set(ransomNote[i],1)
}else{
map.set(ransomNote[i],map.get(ransomNote[i])+1)
}
}
let count = ransomNote.length
for(let i = 0;i<magazine.length;i++){
if(map.has(magazine[i])&&map.get(magazine[i])>0){
map.set(magazine[i],map.get(magazine[i])-1)
count--
}
if(count==0){
return true
}
}
return false
};
15. 三数之和
做过好几遍了, 还是很多细节第一次会写错;尤其是变量名写错和双指针交汇忘了这种低级错误,尬住了
/**
* @param {number[]} nums
* @return {number[][]}
*/
//在两数之和的基础上,哈希或双指针
//但关键是, 要返回多个答案, 去重是个大问题
//双指针显然是更为易懂的, 重复的跳过即可
var threeSum = function(nums) {
let l, r
let result = []
let tSum = 0
nums.sort((a,b)=>a-b)
for(let i = 0; i<nums.length;i++){
if(i!=0&&nums[i]==nums[i-1]){
continue
}
r = nums.length -1
for(l = i+1; l< nums.length;l++){
if(l>i+1&&nums[l]==nums[l-1]){
continue
}
tSum = nums[i]+nums[l]
while(nums[r]>-tSum){
r--
}
if(r<=l){//
break;
}
if(tSum+nums[r]==0){
result.push([nums[i],nums[l],nums[r]])
}
}
}
return result
};
18. 四数之和
题目链接:https://leetcode.cn/problems/4sum/
多套一层循环就可以了,注意一下sort函数缺省时会转成字符串
没有做剪枝优化
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
//和四数相加的不同点关键就在输出的不是索引而是元素且要求不重复;
//这样两两相加变两数之和就不可行了
//相加转为三数之和又如何?
var fourSum = function(nums, target) {
nums.sort((a,b)=>a-b)
let result = []
let r ,l
for(let i =0; i< nums.length;i++){
if(i!=0&&nums[i]==nums[i-1]){
continue
}
for(let j = i+1; j<nums.length;j++){
if(j!=i+1&&nums[j]==nums[j-1]){
continue
}
r = nums.length-1
for(l=j+1;l<nums.length;l++){
if(l!=j+1&&nums[l]==nums[l-1]){
continue
}
while(nums[i]+nums[j]+nums[l]+nums[r]>target&&r>l){
r--
}
if(r==l){
break;
}
//console.log(nums[i],nums[j],nums[l],nums[r])
if(nums[i]+nums[j]+nums[l]+nums[r] == target){
result.push([nums[i],nums[j],nums[l],nums[r]])
}
}
}
}
return result
};
总结
哈希表的主要实际的api运用在于set和map的使用(如果是其他语言会多一些),要记牢
哈希表是一种非常好的空间换时间的方法,在字符串异构和多数之和这类问题上有很大作用;
另外,举一反三和问题拆分,转化和简化是做算法题的重要能力;
首先读懂题意,搞明白一些关键的问题:参数,输入是否有序,返回值(是单纯数字还是需要序列,单个还是多个),这些会影响它应当向什么类型转化;