| date | 2024-07-23 |
|---|
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.
First sort the input array. Then use hash map to store the last seen position of a number. Iterate the sorted arrary with two pointer, and use hashmap to find the 3rd number position.
class Solution {
public List> threeSum(int[] nums) {
Arrays.sort(nums);
HashMap lastSeen = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
lastSeen.put(nums[i], i);
}
List> outputs = new LinkedList<>();
for (int i = 0; i < nums.length; ++i) {
for (int j = i+1; j < nums.length; ++j) {
int - nums[i] - nums[j];
Integer pos = lastSeen.get(target);
if (pos != null && pos > j) {
LinkedList output = new LinkedList<>();
output.add(nums[i]);
output.add(nums[j]);
output.add(nums[pos]);
outputs.add(output);
}
// No duplicate, each j must be different
while (j+1 < nums.length && nums[j] == nums[j+1]) {
++j;
}
}
// No duplicate, each i must be different
while (i+1 < nums.length && nums[i] == nums[i+1]) {
++i;
}
}
return outputs;
}
}
This approach didn't use hashmap to store the last seen position. Select first number first, then on its right, use left/right pointer goes to middle approach.
class Solution {
public List> threeSum(int[] nums) {
Arrays.sort(nums);
List> outputs = new LinkedList<>();
for (int i = 0; i < nums.length;) {
int
int j = i+1, k = nums.length - 1;
while (j < k) {
int diff = nums[j] + nums[k] - target;
if (diff == 0) {
List output = new ArrayList<>();
output.add(nums[i]);
output.add(nums[j]);
output.add(nums[k]);
outputs.add(output);
++j;
--k;
// no diff, each j and k must be different
while(j < nums.length && nums[j-1] == nums[j]) ++j;
while(k >= 0 && nums[k] == nums[k+1]) --k;
} else if (diff > 0) {
--k;
} else {
++j;
}
}
++i;
// no diff, each i must be different
while(i < nums.length && nums[i-1] == nums[i]) ++i;
}
return outputs;
}
}