The question
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.
The idea
Array must be sorted.
Iterate through the list + Left and right pointer.
Result must be a set because they may be duplicate values.
Order of the tuple (current value, left pointer, right pointer) inserted into result matters.
Python
class Solution :
def threeSum ( self , nums : List [ int ]) -> List [ List [ int ]]:
result = set ()
nums . sort ()
for i in range ( len ( nums ) - 2 ):
currentValue = nums [ i ]
left = i + 1
right = len ( nums ) - 1
while left < right :
totalSum = currentValue + nums [ left ] + nums [ right ]
if totalSum > 0 :
right -= 1 // if there is no negative value , left += 1 will only increase totalSum
elif totalSum < 0 :
left += 1
else :
result . add (( currentValue , nums [ left ], nums [ right ]))
left += 1
right -= 1
return result
Enter fullscreen mode
Exit fullscreen mode
Java
class Solution {
public List < List < Integer >> threeSum ( int [] nums ) {
Arrays . sort ( nums );
Set < List < Integer >> set = new HashSet <>();
for ( int i = 0 ; i < nums . length - 2 ; i ++) {
int currentValue = nums [ i ];
int start = i + 1 ;
int end = nums . length - 1 ;
while ( start < end ) {
int total = currentValue + nums [ start ] + nums [ end ];
if ( total < 0 ) {
start += 1 ;
} else if ( total > 0 ) {
end -= 1 ;
} else {
set . add ( Arrays . asList ( currentValue , nums [ start ], nums [ end ]));
start += 1 ;
end -= 1 ;
}
}
}
return new ArrayList <>( set );
}
}
Enter fullscreen mode
Exit fullscreen mode
Top comments (0)