【代码随想录算法训练营】d7 454.四数相加 383.赎金信 15. 三数之和 18. 四数之和_浅夏、的博客-爱代码爱编程
今日题目:
- 454.四数相加
- 383.赎金信
- 15. 三数之和
- 18. 四数之和
解题思想:
- 数组分组,巧用哈希表
454题四数相加,哈希表的经典题目,因为需要判断某个元素是否在表中出现过,所以自然想到哈希表。这道题有个很关键的地方,答案无需去重,因为相同数字放在数组不同位置,它们也是不同的。4个数组,两两一组,先遍历nums1和nums2,在map中记录它们的答案和出现次数,再遍历nums3和nums4,寻找它们的和的负数是否在map中出现。
注意,当在map寻找到对应的值时,并不是直接简单count++,因为答案无需去重,所以应该加的是对应值对应的value
比较巧妙的地方是数组两两分组,这样可以有效降低时间复杂度。
- 双指针法
15题三数之和难点是在去重上,用哈希表的话在去重上比较困难,所以这里选择双指针。
首先对数组进行排序,排序之后使用一轮for循环,先确定第一个数,再这个数后面的区间中利用双指针寻找符合条件的答案。
三个位置的指针都需要去重处理。我们需要求的是不能重复的三元组,但三元组里面的元素是可以重复的。
对i的去重逻辑,是让它与前一个位置对比,看是否相同。对L和R指针的去重逻辑,一定要先收获一个结果再去判断下一个值是否重复,比如数组[0,0,0,0,0],如果先去重处理再收获结果,那么L和R指针直到相遇也没有收获一个结果。
- 去重与剪枝
四数之和,思路大体和三数之和相似,比它多套一层循环。但是本题求的target不是固定的数,它可能为负数,所以剪枝的时候不能直接
if(nums[i]>target) break
。
四个指针都需要进行对应的去重处理,i>0 && nums[i]==nums[i-1]
,j>i+1 && nums[j]==nums[j-1]
注意这里是j>i+i
,因为j的初始位置是设置为i+1
,自己在做的时候犯了一个小错,把条件设置为了j>i
。
代码:
- 454.四数相加
var fourSumCount = function(nums1, nums2, nums3, nums4) {
const map = new Map()
let count = 0
for(const n1 of nums1) {
for(const n2 of nums2) {
const sum = n1+n2
map.set(sum, (map.get(sum)||0) + 1)
}
}
for(const n3 of nums3) {
for(const n4 of nums4) {
const sum = n3+n4
count +=(map.get(-sum) || 0)
}
}
return count
};
- 383.赎金信
var canConstruct = function(ransomNote, magazine) {
const map = new Map()
for(const letter of magazine) {
map.set(letter, (map.get(letter)||0)+1 )
}
for(const letter of ransomNote) {
if(!map.get(letter) ||map.get(letter)<0) return false
map.set(letter, (map.get(letter)||0)-1 )
}
return true
};
-
- 三数之和
var threeSum = function(nums) {
nums.sort((a,b) => a-b)
const res = []
for(let i =0; i<nums.length; i++) {
if(nums[i]>0) return res
if(i>0 && nums[i] == nums[i-1]) continue //对i去重
let L = i+1
let R = nums.length-1
while(L<R) {
let sum = nums[i] + nums[L] + nums[R]
if(sum ==0 ) {
res.push([nums[i], nums[L], nums[R]])
while(nums[L] == nums[L+1] && L<R) L++ //对L去重
while(nums[R] == nums[R-1] && L<R) R-- //对R去重
L++
R--
}
if(sum>0){
R--
}
if(sum <0){
L++
}
}
}
return res
};
-
- 四数之和
var fourSum = function(nums, target) {
nums.sort((a,b) => a-b)
const res = []
for(let i=0; i<nums.length-3; i++) {
if(nums[i]>target && target>0) break //一级剪枝
if(i>0 && nums[i]== nums[i-1]) continue //对i去重处理
for(let j=i+1; j<nums.length-2; j++) {
let twoSum = nums[i]+nums[j]
if(twoSum>target && target>0) break //二级剪枝
if(j>i+1 && nums[j] == nums[j-1]) continue //对j去重处理
let L = j+1
let R = nums.length-1
while(L<R){
let fourSum = twoSum+nums[L]+nums[R]
if(fourSum == target) {
res.push([nums[i], nums[j], nums[L], nums[R]])
while(L<R && nums[L] == nums[L+1]) L++
while(L<R && nums[R] == nums[R-1]) R--
L++
R--
}
if(fourSum>target) R--
if(fourSum<target) L++
}
}
}
return res
};
总结:
不难发现三数之和和四数之和的做法都是有固定模式的,先固定一个或两个指针,再在剩余区间内用左右两指针不断探测符合条件的结果集,并且对每个指针都需要去重处理。但是去重的地方一定要想清楚,到底是与前面的指针相判断、还是后面的指针相判断、是先收获结果再去重还是先去重再收获结果。为了提高算法效率,还可以进行适当剪枝操作。
自己在做四数之和的时候,思路是对的,但是忽略了target值可能为负数的情况,剪枝错误导致一些用例不通过,说明自己对题目的细节把控还是不太到位。今天的题目还是需要多次练习巩固。