This content originally appeared on DEV Community and was authored by MING
This Blog aims to list all possible solution patterns for this type of leetcode interview question: 2Sum, 3Sum, 4Sum ...K-Sum.
Pattern for typical 2Sum
🕹Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. leetcode link
Example:
Input: nums = [2,7,11,15], target = 9 Output:[0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
- Brute force
If we don't consider any quicker solution yet, believe the double loop could be pop out first in the mind.
so we the outer for-loop is start from index 0, the inner for-loop is start from index 1, then see the if the sum of two adjacent elements is equal to target.
var twoSum = function(nums, target) {
for(let i=0; i<nums.length; i++){
for(let j=i+1; j<nums.length; j++){
if(nums[i]+nums[j]===target)
return [i, j]
}
}
return [-1,-1]
};
- Hash-map
/* Pattern:
1. Build a hash map which save the difference(target-
eachElement in the arry) as key, index as value.
2. Iterate the arrya, to see if the difference(target-
eachElement in the arry) is in the hasp map.
2.1 if the difference existed in the hash map, return index
2.2 if the difference didn't existed in the hash map, then
save the difference to the hash map for future use
(update the hash map)
*/
var twoSum = function (nums, target) {
let seen = new Map();
for (let i = 0; i < nums.length; i++) {
let diff = target - nums[i];
if (seen.has(diff)) return [i, seen.get(diff)];
seen.set(nums[i], i);
}
};
- 2 Pointers
Please be aware the 2-pointer pattern can be used when the array is sorted, you can refer to 2sum II leetcode problem. which is exactly same with out current 2sum problem but array is sorted.
var twoSum = function(nums, target) {
let left = 0; //1.scope set
let right = nums.length -1; //1.scope set
while(left < right){ //2.while end condition
let sum = nums[left]+nums[right]; //3.guess answer
if(sum === target){ //4.check answer
return [left,right]
}else if(sum<target){ //5.adjust scope
left++
}else if(sum>target){
right-- //5.adjust scope
}
}
return[-1,-1]
};
Pattern for 3Sum
🕹Problem: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
- Sort + 2pointers thinking
we still can use 2 pointer to solve 2 sum, instead of using 2 pointers we use 3 pointers here, 1 pointer is locked, and do 2 sum with others 2 pointers.
/* Pattern:
1. sorted the array.
2. lock one pointer, and do 2sum with the other two
*/
var threeSum = function(nums) {
let result = [];
nums.sort((a,b)=>a-b);
if(nums.length<3) return result;
for(let i=0; i<nums.length-2; i++ ){
if(i>0 && nums[i]===nums[i-1]) continue; //skip duplicated
let low = i+1;
let high = nums.length-1;
//nums[i] is pointer1,low is pointer2,high is pointer3
while(low<high){
if(nums[i]+nums[low]+nums[high]===0){
result.push([nums[i],nums[low],nums[high]]);
while(low<high && nums[low]===nums[low+1]) {
low++; //remove all duplicated
}
while(low<high && nums[high]===nums[high-1]) {
high--; //remove all duplicated
}
low++;
high--;
}else if(nums[i]+nums[low]+nums[high]<0){
low++;
}else{
high--;
}
}
}
return result;
};
Pattern for 3Sum Closest
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
/*
Pattern: based on above sort Array + 2 pointers
the big difference is while loop's duty changed
*/
var threeSumClosest = function (nums, target) {
nums.sort((a, b) => a - b);
let distance = Infinity;
let sum = 0;
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; //skip dup
let low = i + 1;
let high = nums.length - 1;
while (low < high) {
let currSum = nums[i] + nums[low] + nums[high];
if (Math.abs(currSum - target) < distance) {
sum = currSum;
distance = Math.abs(currSum - target);
}
(currSum < target) ? low++ : high--;
}
}
return sum;
};
Pattern for 3Sum Smaller
Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < nthat satisfy the condition nums[i] + nums[j] + nums[k] < target.
Example:
Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3]
/* Pattern: based on above sort Array + 2 pointers */
var threeSumSmaller = function(nums, target) {
let count=0;
nums.sort((a,b)=>a-b);
for(let i=0; i<nums.length-2; i++){
let low = i+1;
let high = nums.length-1;
while(low<high){
let sum = nums[i]+nums[low]+nums[high];
if(sum<target){
count+=(high-low)
low++;
}else{
high--;
}
}
}
return count
};
Pattern for 4Sum
🕹Problem: Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
/* Pattern:
1. sorted the array.
2. lock 2 pointer, and do 2Sum with the other two
*/
var fourSum = function (nums, target) {
let result = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 3; i++) { //lock pointer 1
if (i > 0 && nums[i] === nums[i - 1]) continue; //skip dup
//lock pointer 2
for (let j = i + 1; j < nums.length - 2; j++) {
//skip dup
if (nums[j] === nums[j - 1] && j !== i + 1) continue;
let low = j + 1;
let high = nums.length - 1;
while (low < high) {
let sum = nums[i] + nums[j] + nums[low] + nums[high];
if (sum === target) {
result.push([nums[i],nums[j],nums[low],nums[high]]);
while (low < high && nums[low] === nums[low + 1])
{ low++; }
while (low < high && nums[high] === nums[high - 1])
{ high--; }
low++;
high--;
} else if (sum < target) {
low++;
} else {
high--;
}
}
}
}
return result;
};
This content originally appeared on DEV Community and was authored by MING
MING | Sciencx (2022-02-11T19:31:14+00:00) K Sum- JS. Retrieved from https://www.scien.cx/2022/02/11/k-sum-js/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.