算法篇——N个数之和大集合(js版)
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
链接:https://leetcode.cn/problems/two-sum
var twoSum = function(nums, target) {var indexList = [];var map = new Map();for(var i = 0; i < nums.length; i++) {// 遍历当前值时去找Map中可以得到目标值的加数var add = map.get(target - nums[i]);// 能找到就放入结果数组if(add != null) {indexList.push(add, i);return indexList;}// 否则将当前值放入map中map.set(nums[i], i);}
};
//2:0
15.三数之和
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
链接:https://leetcode.cn/problems/3sum
var threeSum = function(nums) {var numList = [];var nList = nums.sort((a, b) => a - b);// 如果有序数组第一个元素大于0,则返回nullif(nList[i] > 0) return numList;for(var i = 0; i < nList.length; i++) {var left = i + 1, right = nums.length - 1;// 去重if(nList[i] == nList[i - 1]) continue;while(left < right) {var sum = nList[left] + nList[i] + nList[right];// 说明三数之和大了,right向左移动if(sum > 0) right--;// 说明三数之和小了,left向右移动else if(sum < 0) left++;else {numList.push([nList[i], nList[left], nList[right]]);// 去重while(nList[left] == nList[left + 1]){left++;}while(nList[right] == nList[right - 1]) {right--;}left++right--;}} }return numList;
};
18.四数之和
给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
链接:https://leetcode.cn/problems/4sum
var fourSum = function(nums, target) {var numList = [];var nList = nums.sort((a, b) => a - b);// 达不到四数之和的要求if(nums.length < 4) return numList;for(var i = 0; i < nList.length - 3; i++) {// 去重if(i > 0 && nList[i] == nList[i - 1]) continue;for(var j = i + 1; j < nList.length - 2; j++) {// 去重if(j > i + 1 && nList[j] == nList[j - 1]) continue;var left = j + 1, right = nList.length - 1;while(left < right) {var sum = nList[i] + nList[j] + nList[left] + nList[right];// 说明和大了,right向左移动if(sum > target) right--;// 说明和小了,left向右移动else if(sum < target) left++;else {numList.push([nList[i], nList[j], nList[left], nList[right]]);// 去重while(nList[left] == nList[left + 1]){left++;}while(nList[right] == nList[right - 1]) {right--;}left++right--;}} }}return numList;
};
454.四数相加Ⅱ
给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
链接:https://leetcode.cn/problems/4sum-ii
var fourSumCount = function(nums1, nums2, nums3, nums4) {var map = new Map();var count = 0;// 前两个数组的求和遍历for(var i1 of nums1) {for(var i2 of nums2) {var sum = i1 + i2;// 和作为key,次数作为valuemap.set(sum, (map.get(sum) || 0) + 1)}}// 后两个数组的求和遍历for(var i3 of nums3) {for(var i4 of nums4) {var sum = i3 + i4;// 和作为key,次数作为valuecount += (map.get(-sum) || 0);}}return count;
};