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] <= 105class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
Map<Integer, Integer> map = new HashMap<>();
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < n; i++)
map.put(nums[i], i);
for (int i = 0; i < n; i++) {
if (i != 0 && nums[i] == nums[i - 1])
continue;
for (int j = i + 1; j < n; j++) {
if (j != i + 1 && nums[j] == nums[j - 1])
continue;
int k = map.getOrDefault(-(nums[i] + nums[j]), 0);
if (k > j)
ans.add(List.of(nums[i], nums[j], nums[k]));
}
}
return ans;
}
}class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Set<List<Integer>> ans = new HashSet<>();
for (int i = 0; i < n; i++) {
Set<Integer> set = new HashSet<>();
for (int k = i + 1; k < n; k++) {
if (set.contains(-(nums[i] + nums[k]))) {
List<Integer> l = Arrays.asList(nums[i], -(nums[i] + nums[k]), nums[k]);
l.sort(null);
ans.add(l);
}
set.add(nums[k]);
}
}
return new ArrayList<>(ans);
}
}class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) // skip dup
continue;
for (int j = i + 1, k = n - 1; j < k;) { // 2 ptr
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
k--;
while (j < k && nums[j] == nums[j - 1]) // skip dup
j++;
while (j < k && nums[k] == nums[k + 1]) // skip dup
k--;
} else if (sum < 0)
j++;
else
k--;
}
}
return ans;
}
}