You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
functionthreeSum(nums){constresults=[]// obviously irrelevant if we don't have at least 3 numbers to play with!if(nums.length<3)returnresults// having the numbers in ascending order will make this problem much easier.// also, knowing the overall problem will take at least O(N^2) time, we can// afford the O(NlogN) sort operationnums=nums.sort((a,b)=>a-b)// if the question asks us for a custom target, we can control it herelettarget=0for(leti=0;i<nums.length-2;i++){// `i` represents the "left" most number in our sorted set.// once this number hits 0, there's no need to go further since// positive numbers cannot sum to a negative numberif(nums[i]>target)break// we don't want repeats, so skip numbers we've already seenif(i>0&&nums[i]===nums[i-1])continue// `j` represents the "middle" element between `i` and `k`.// we will increment this up through the array while `i` and `k`// are anchored to their positions. we will decrement `k` for// for each pass through the array, and finally increment `i`// once `j` and `k` meet.letj=i+1// `k` represents the "right" most elementletk=nums.length-1// to summarize our setup, we have `i` that starts at the beginning,// `k` that starts at the end, and `j` that races in between the two.//// note that `i` is controlled by our outer for-loop and will move the slowest.// in the meantime, `j` and `k` will take turns inching towards each other depending// on some logic we'll set up below. once they collide, `i` will be incremented up// and we'll repeat the process.while(j<k){letsum=nums[i]+nums[j]+nums[k]// if we find the target sum, increment `j` and decrement `k` for// other potential combos where `i` is the anchorif(sum===target){// store the valid threesumresults.push([nums[i],nums[j],nums[k]])// this is important! we need to continue to increment `j` and decrement `k`// as long as those values are duplicated. in other words, we wanna skip values// we've already seen. otherwise, an input array of [-2,0,0,2,2] would result in// [[-2,0,2], [-2,0,2]].//// (i'm not a fan of this part because we're doing a while loop as we're// already inside of another while loop...)while(nums[j]===nums[j+1])j++while(nums[k]===nums[k-1])k--// finally, we need to actually move `j` forward and `k` backward to the// next unique elements. the previous while loops will not handle this.j++k--// if the sum is too small, increment `j` to get closer to the target}elseif(sum<target){j++// if the sum is too large, decrement `k` to get closer to the target}else{// (sum > target)k--}}}returnresults};
The text was updated successfully, but these errors were encountered:
kyxg
added a commit
to kyxg/FrontEndCollection
that referenced
this issue
Jan 4, 2022
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.
The text was updated successfully, but these errors were encountered: