1.四数相加II

题目描述

解题思路

1.定义一个哈希Map,其中key存放两数之和，value存放两数和出现的次数。
2.遍历统计出nums1和nums元数相加和出现的次数(a+b)。
3.遍历nums3和nums4，并求和(c+d),统计出(0-(c+d))在Map中出现的次数。
4.返回（0-(c+d)）出现次数的累加和。

var fourSumCount = function(nums1, nums2, nums3, nums4) {let map = new Map()let result = 0;for(let i = 0;i<nums1.length;i++) {for(let j = 0;j<nums2.length;j++) { // 统计前两个数组元素之和let tmp = nums1[i] + nums2[j]if(map.has(tmp)){map.set(tmp,map.get(tmp) + 1)} else {map.set(tmp,1)}}}for(let i=0;i<nums3.length;i++) {for(let j = 0;j<nums4.length;j++) {let tmp = nums3[i] + nums4[j]if(map.has(0-tmp)){ // 如果map中存在 说明四数相加等于0result += map.get(0-tmp)}}}return result
};

2.赎金信

题目描述

解题思路

1.定义一个哈希Map，其中key存放ransomNote中的每个字母，value表示每个字母出现的次数。
2.遍历ransomNote字符串，统计每个字母出现的次数。
3.遍历magazine字符串，Map中的每个字母减去对应的次数。
4.遍历map，判断是否有字母出现次数大于0，有则返回false,否则返回true.

var canConstruct = function(ransomNote, magazine) {let map = new Map();for(let i = 0;i<ransomNote.length;i++) {map.set(ransomNote[i],(map.get(ransomNote[i])|| 0)+1)}for(let i = 0;i<magazine.length;i++) {if(map.has(magazine[i])) {map.set(magazine[i],map.get(magazine[i]) - 1)}}for(let [k,v] of map) {if(v > 0) {return false}}return true
};

3.三数之和

题目描述

解题思路

1.将数组按照从小到大的顺序排序。
2.遍历数组，在循环中使用双指针，其中左指针表示循环索引+1，右指针为数组末位索引。
3.判断nums[i]+nums[left]+nums[right]=sum和与0的大小。
4.如果sum>0，则右指针左移，如果sum<0，左指针右移，如果sum==0,将对应数据添加入结果中。
5.下次循环继续如此操作,循环中注意去重剪枝。

var threeSum = function(nums) {let result = [];nums = nums.sort((a,b) => a-b)for(let i = 0;i<nums.length;i++) {if(nums[i] > 0) {return result}if(i>0&&nums[i] == nums[i-1]) {continue}let left = i + 1;let right = nums.length -1while(left<right) { // i j k 不相等 所以这儿不能又等于let tmp = nums[i] + nums[left] + nums[right]if(tmp > 0) {right --} else if(tmp<0) {left ++} else {result.push([nums[i],nums[left],nums[right]])while(left<right && nums[right] == nums[right - 1]) right--while(left<right && nums[left] == nums[left+1]) left++ // 去重left ++right -- // 区间缩小}}}return result
};

4.四数之和

题目描述

解题思路

本题解题思路和三数之和相同，只需将外部循环改为双重循环即可。

var fourSum = function(nums, target) {nums = nums.sort((a,b) => a- b);const result = [];for(let i = 0;i<nums.length;i++) {if(nums[i]>target&&target>0){break; // 剪枝}if(i>0&&nums[i] === nums[i-1]){continue; // 去重}for(let j = i+1;j<nums.length-1;j++){if(nums[i] + nums[j] > target&&target>0){break; // 剪枝}if(j>i+1&&nums[j] == nums[j-1]){continue // 去重}const twoSum = nums[i] + nums[j]let left = j+1;let right = nums.length-1while(left<right){if(twoSum + nums[left]+nums[right] === target) {result.push([nums[i],nums[j],nums[left],nums[right]])while(right>left&&nums[right] == nums[right-1]) {right--}while(right>left&&nums[left] == nums[left+1]){left++}left++right--;} else if(twoSum + nums[left] + nums[right] > target) {right --} else  {left++;}} }}return result
};