15. 3Sum
3Sum
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.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105
Approach) Contracting window
In this solution, we start by sorting the array and then looping through all of the numbers (excluding the last 2, as we need 3 numbers to be able to make a 3-number sum). For each number, we then establish a window, with its left-hand side immediately after the initial number, and its right-hand side at the end of the array. We then sum together the 3 chosen numbers.
If the sum of the 3 numbers is 0 (our target), we add this solution to the pile of solutions, and then move our window in on both the left and right sides (because if we only moved it in on one side, it would be impossible for it to be a solution).
If however, the sum of all 3 numbers is not 0, then we only need to move one side in. If the sum is more than 0, then the right-hand side of the window is brought to the left. If the sum is less than 0, the left-hand side of the window is pushed to the right.
One key part of these 3 stages is the fact that we always move until the numbers change. In other words, when we find a solution, we don’t just move the left and right-hand sides 1 place in because the numbers may remain the same, so we move them until the numbers change.
The reason for this is that we’re asked to find unique solutions, so we cannot simply return the same 3 numbers just because they are in different places.
Let`s code it!
var threeSum = function (nums) {
// Initialise an array to store the solutions
let solutionArrays = [];
// Sort the array
const sortedNums = nums.sort((a, b) => a - b);
// Loop through the array (excluding the last 2 entries)
for (let i = 0; i < sortedNums.length - 2; i++) {
// Break out if the first number is higher than 0 (as no sum of 3 can then equal 0)
if (sortedNums[i] > 0) {
break;
}
// Skip this number if it is a repeat of the last one
if (i > 0 && sortedNums[i] == sortedNums[i - 1]) {
continue;
}
// Establish a window from the next number to the end of the array
let left = i + 1;
let right = sortedNums.length - 1;
// Run until the window is closed
while (left < right) {
// Add together the current number, and each side of the window
const subTotal =
sortedNums[left] + sortedNums[right] + sortedNums[i];
// If we've reached an answer, add it to the array of answers
if (subTotal == 0) {
solutionArrays.push([
sortedNums[i],
sortedNums[left],
sortedNums[right],
]);
// Move the left-hand edge of the window to the right until it reaches a different number
do {
left++;
} while (sortedNums[left] == sortedNums[left - 1]);
// Move the right-hand edge of the window to the left until it reaches a different number
do {
right--;
} while (sortedNums[right] == sortedNums[right + 1]);
}
// If we're too low
else if (subTotal < 0) {
left++;
} else {
right--;
}
}
}
return solutionArrays;
};function threeSum(nums) {
// If less than 3 elements then we can't have 3 numbers that add to 0
if(nums.length < 3) return []
const output = []
// Sort the array in descending order. Must add order function to sort. If not we will not get the right order. Sort converts everything to a string and sorts the array by charCode. Adding the order function to sort guarantees we will get the array in the proper descending order.
nums.sort((a,b) => a - b)
for(let i = 0; i < nums.length - 2;i++) {
// we don't want repeats, so skip numbers we've already seen
if (i > 0 && nums[i] === nums[i - 1]) continue
let left = i+1
let right = nums.length-1
// Current number at i will be added to the current sum. We will move a left and a right pointer in the subarray of elements to the right of i to try and get a sum that will equal 0
while (left < right) {
// Get the current sum with with number at i and numbers at the left and right pointers
const sum = nums[i] + nums[right] + nums[left]
// If we get 0 then we add all the numbers to output and move our left and right pointers to look for more numbers that will add to 0 with the current number at i
if(sum===0) {
output.push([nums[i], nums[left], nums[right]])
// We will move the pointers until we find a number that is not equal to each pointers current number
while(nums[left]===nums[left+1]) left++
while(nums[right]===nums[right+1]) right--
left++
right--
} else if (sum > 0) {
// If the sum is greater than 0 that means we need smaller numbers to get 0 so we move the right pointer to the left
right--
} else {
// If the sum is less than 0 that means we need higher numbers to get 0 so we move the left pointer to the right
left++
}
}
}
return output
};That’s all folks! In this post, we solved LeetCode problem #15. 3Sum
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment