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.
Constraints:
- -10^5 <= nums[i] <= 10^5
- 0 <= i < nums.length
- 0 <= j < nums.length
- 0 <= k < nums.length
- i != j
- i != k
- j != k
Examples:
Input: [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: The triplets that sum to zero are [-1, -1, 2] and [-1, 0, 1].
Solutions
Two Pointers
Time: O(n^2)Space: O(n)
The two pointers approach is used to solve this problem. First, the array is sorted. Then, for each element in the array, two pointers are used to find a pair of elements that sum to the negation of the current element. If the sum is less than zero, the left pointer is moved to the right. If the sum is greater than zero, the right pointer is moved to the left. If the sum is equal to zero, the triplet is added to the result and the pointers are moved.
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0;
i < nums.length - 2;
i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) left++;
else if (sum > 0) right--;
else {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return result;
}Follow-up:
4Sum
