Locate a triplet in an array that sums to a specified value (3-sum).

This question presents an array of integers along with a target value, ‘sum’. Your task is to identify three elements within the array that total the specified sum, a challenge commonly known as the 3-sum problem in coding interviews. Depending on the details of the question, you may need to find either a single triplet or all possible triplets. A good strategy for tackling this question is to first think about how you would approach a related but simpler problem: finding two numbers that add up to a given sum. This can be accomplished by sorting the array and employing a two-pointer technique—one pointer starts at the beginning of the array while the other starts at the end. Depending on the combined value of the elements at these pointers, you would either advance the start pointer (if the sum is less than the target) or retract the end pointer (if the sum is greater). To locate three numbers (a triplet) that sum to the specified value, we can build on this method. We select one number and then search for two additional numbers that sum to the remaining amount, again utilizing the two-pointer technique on the rest of the array. This process must be repeated for every number in the array to uncover all potential triplets. It’s also important to manage duplicates in this problem since we cannot have repeated triplets in our results. To avoid counting the same numbers multiple times, we can skip over duplicate entries.

Here is a sample solution written in Python: def threeSum ( nums , target ) : nums . sort ( ) res = [ ] for i in range ( len ( nums ) - 2 ) : if i > 0 and nums [ i ] == nums [ i - 1 ] : continue l , r = i + 1 , len ( nums ) - 1 while l < r : s = nums [ i ] + nums [ l ] + nums [ r ] if s < target : l += 1 elif s > target : r -= 1 else : res . append ( ( nums [ i ] , nums [ l ] , nums [ r ] ) ) while l < r and nums [ l ] == nums [ l + 1 ] : l += 1 while l < r and nums [ r ] == nums [ r - 1 ] : r -= 1 l += 1 ; r -= 1 return res In this approach, we start by sorting the input array. We then loop through each element and utilize a two-pointer technique on the remaining part of the array to identify pairs that add up to the total target sum minus the current element.

Here is another Java solution: public class Main { public List < List < Integer > > threeSum ( int [ ] nums , int target ) { Arrays . sort ( nums ) ; List < List < Integer > > res = new ArrayList < > ( ) ; for ( int i = 0 ; i < nums . length - 2 ; i ++ ) { if ( i == 0 || ( i > 0 && nums [ i ] != nums [ i - 1 ] ) ) { int low = i + 1 ; int high = nums . length - 1 ; int sum = target - nums [ i ] ; while ( low < high ) { if ( nums [ low ] + nums [ high ] == sum ) { res . add ( Arrays . asList ( nums [ i ] , 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 ( nums [ low ] + nums [ high ] < sum ) { low ++ ; } else { high -- ; } } } } return res ; } } This Java implementation uses the same methodology as the Python version: it sorts the array, iterates through it, and for each element, employs a two-pointer strategy to identify pairs that sum to the target minus the current element.