3Sum
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.
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-10^5 <= nums[i] <= 10^5
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; ++i){
int targetSum = -nums[i];
int j = i + 1, k = nums.length - 1;
while(j < k){
if(nums[j] + nums[k] == targetSum){
result.add(List.of(nums[i], nums[j], nums[k]));
while(j < k && nums[j] == nums[j + 1]) ++j;
while(j < k && nums[k] == nums[k - 1]) --k;
++j;
--k;
}else if(nums[j] + nums[k] < targetSum){
++j;
}else{
--k;
}
}
while(i < nums.length - 1 && nums[i] == nums[i + 1]) ++i;
}
return result;
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const result = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; ++i) {
const targetSum = -nums[i];
let j = i + 1;
let k = nums.length - 1;
while (j < k) {
if (nums[j] + nums[k] === targetSum) {
result.push([nums[i], nums[j], nums[k]]);
while (j < k && nums[j] === nums[j + 1]) ++j;
while (j < k && nums[k] === nums[k - 1]) --k;
++j;
--k;
} else if (nums[j] + nums[k] < targetSum) {
++j;
} else {
--k;
}
}
while (i < nums.length - 1 && nums[i] === nums[i + 1]) ++i;
}
return result;
};
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]:
continue
target_sum = -nums[i]
j = i + 1
k = len(nums) - 1
while j < k:
if nums[j] + nums[k] == target_sum:
result.append([nums[i], nums[j], nums[k]])
while j < k and nums[j] == nums[j + 1]:
j += 1
while j < k and nums[k] == nums[k - 1]:
k -= 1
j += 1
k -= 1
elif nums[j] + nums[k] < target_sum:
j += 1
else:
k -= 1
return result
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
int targetSum = -nums[i];
int j = i + 1;
int k = nums.size() - 1;
while (j < k) {
if (nums[j] + nums[k] == targetSum) {
result.push_back({nums[i], nums[j], nums[k]});
while (j < k && nums[j] == nums[j + 1])
++j;
while (j < k && nums[k] == nums[k - 1])
--k;
++j;
--k;
} else if (nums[j] + nums[k] < targetSum) {
++j;
} else {
--k;
}
}
}
return result;
}
};
Time/Space Complexity:
- Time Complexity: O(n^2)
- Space Complexity: O(1)
Explanation:
We have constant space complexity (the end result we're returning from the function usually doesn't count towards the space complexity), and we spend O(nlogn) for sorting the array, but we spend O(n^2) with the two loops so that leads us to quadratic time complexity. We're searching for the triplet, so our first hint should be to either use some kind of data structure to remember occurrences of elements and check if they add up to targetSum (in our case if we pick first number val we have to find a pair that sums up to -val, so that's our targetSum) or to utilize the order in sorted array. If the array is sorted we utilize the two pointers approach where we start with two pointers at each end of the sorted array and check if they're pointing to elements adding up to some sum, if not we try to either decrease the pointer from the end or increase the pointer from the start depending if the current sum is smaller or larger than the target sum (note that moving an index pointing to the start to the right would increase the current sum, since the array is sorted, while moving the pointer showing to the end to the left would decrease the current sum). The tricky part is to skip the duplicate triples, but order/sorted-ness of the array helps us there too, since we can just check if the current element pointer is pointing to is same as next or previous element (depending on if it's the i or j pointer) and we can just skip element until we find a non-duplicate element.