454. 四数相加 II
解题思路
- 定义哈希表 map
- 记录
nums1和nums2各个元素两两相加和及出现的次数，key=和，value=和出现的次数。 - 记录
nums2和nums3各个元素两两相加和，如果map存在0 - (k + l)的key，说明满足nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0，由于不需要考虑重复元素，统计其出现的次数即可。
var fourSumCount = function(nums1, nums2, nums3, nums4) {
let map = new Map();
for (let i of nums1) {
for (let j of nums2) {
map.set(i+j, (map.get(i+j) || 0) + 1)
}
}
let count = 0;
for (let k of nums3) {
for (let l of nums4) {
count += map.get(0 - (k+l)) || 0
}
}
return count;
};
383. 赎金信
解题思路
实现一
- 哈希解法 - Map
- 由于
magazine中的每个字母只能在ransomNote中使用一次，所以至少要统计magazine中各个字母出现的次数。 - 遍历
ransomNote，如果ransomNote中的字母不存在map中或者次数已用完，说明ransomNote所需要的字母magazine不能满足，返回false；。
var canConstruct = function(ransomNote, magazine) {
let map = new Map()
for (let i of magazine){
map.set(i,(map.get(i) || 0)+1)
}
for(let i of ransomNote){
if (!map.get(i)) {
return false;
}
map.set(i, map.get(i) - 1)
}
return true
};
实现二
- 哈希解法 - Array
- 由于题目说明
ransomNote和magazine由小写英文字母组成，所以最大长度是可以确定为26的。 - 在长度可以确定的情况下，由于使用
Map的空间消耗要比Array大一些的，因此可以使用数组求解。
var canConstruct = function(ransomNote, magazine) {
const strArr = new Array(26).fill(0);
const base = "a".charCodeAt();
for (let i of magazine) {
strArr[i.charCodeAt() - base]++;
}
for (let i of ransomNote) {
const index = i.charCodeAt() - base;
if (!strArr[index]) {
return false
}
strArr[index]--
}
return true
};
15. 三数之和
解题思路
- 特殊判断，
if (nums.length < 3) return false - 对
nums排序，从索引i = 0开始，使用双指针依次求和，收缩后续元素 -
left = i + 1，right = nums.length - 1 if (arr[left] + arr[right] + arr[i] < 0) left++if (arr[left] + arr[right] + arr[i] > 0) right---
else保留一组结果值
难点
目标找出a + b + c = 0，且不可以包含重复的三元组，注意 [0,0,0,0]
a = nums[i], b = nums[left], c = nums[right]
- 去重
去重a：if (i > 0 && arr[i]==arr[i-1]) continue
去重b：while(left < right && arr[left] === arr[left+1]) { left++ }
去重c：while(left < right && arr[right] === arr[right-1]) { right-- }
var threeSum = function(nums) {
if (nums.length < 3) {
return []
}
let arr = nums.sort((a, b) => a - b)
let left = 0;
let right = arr.length - 1;
let res = []
for(let i = 0;i<arr.length;i++){
// 如果排序后的第1个元素大于0，那么不可能凑成满足条件的三元组
if(arr[i]>0) {
return res
}
// 错误去重a方法，将会漏掉-1,-1,2 这种情况
/*
if (nums[i] == nums[i + 1]) {
continue;
}
*/
if(i>0 && arr[i]==arr[i-1]) {
continue
}
left = i+1
right = arr.length - 1
while(left < right) {
if (arr[left]+arr[right] +arr[i] < 0){
left++
} else if(arr[left]+arr[right] +arr[i] > 0){
right--
} else {
// 优先保存一组满足条件的元组
res.push([arr[i],arr[left],arr[right]])
// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
while(left < right && arr[left] === arr[left+1]) {
left++
}
while(left < right && arr[right] === arr[right-1]) {
right--
}
left++
right--
}
}
}
return res;
};
18. 四数之和
解题思路
- 本题同15. 三数之和类似，看上去多了一层循环。
- 注意目标值
target不再是0，有可能是负数，比如排序后的数组arr = [-4, -3, -2, -1]，target = -10，那么arr[0] > target，但是仍然存在满足条件的元组。 - 第一层剪枝，满足
if(arr[i]>target && (arr[i] >= 0 || target >= 0)) { break }，则说明不会出现满足条件的四元组。 - 第一层去重，同15. 三数之和处理相同。
- 第二层剪枝，
if(arr[i] + arr[j] >target && arr[i] + arr[j] > 0) { break } - 第二层去重，
if (arr[j] === arr[j-1] && j > i+1) { continue } - 剩余处理同15. 三数之和
var fourSum = function(nums, target) {
let arr = nums.sort((a, b) => a - b);
let res = [];
let left = 0;
let right = arr.length - 1;
for (let i = 0; i < arr.length; i++) {
if(arr[i]>target && (arr[i] >= 0 || target >= 0)) { // 一层剪枝
break
}
if (arr[i] === arr[i-1] && i > 0) { // 一层去重
continue
}
for (let j = i+1; j<arr.length; j++) {
if(arr[i] + arr[j] >target && arr[i] + arr[j] > 0) { // 二层剪枝
break
}
if (arr[j] === arr[j-1] && j > i+1) { 二层去重
continue
}
left = j+1
right = arr.length - 1
while(left < right) {
if (arr[left]+arr[right] +arr[i] + arr[j] < target){
left++
} else if(arr[left]+arr[right] +arr[i] + arr[j] > target){
right--
} else {
res.push([arr[i],arr[j],arr[left],arr[right]])
while(left < right && arr[left] === arr[left+1]) {
left++
}
while(left < right && arr[right] === arr[right-1]) {
right--
}
left++
right--
}
}
}
}
return res;
};
