In this post, you will know how to solve the 3Sum Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
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] <= 105
3Sum Leetcode Solutions in Python
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
ans = []
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
l = i + 1
r = len(nums) - 1
while l < r:
summ = nums[i] + nums[l] + nums[r]
if summ == 0:
ans.append((nums[i], nums[l], nums[r]))
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r:
l += 1
while nums[r] == nums[r + 1] and l < r:
r -= 1
elif summ < 0:
l += 1
else:
r -= 1
return ans
3Sum Leetcode Solutions in CPP
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
if (nums.size() < 3)
return {};
vector<vector<int>> ans;
sort(begin(nums), end(nums));
for (int i = 0; i + 2 < nums.size(); ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
// Choose nums[i] as the first num in the triplet,
// and search the remaining nums in [i + 1, n - 1]
int l = i + 1;
int r = nums.size() - 1;
while (l < r) {
const int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
ans.push_back({nums[i], nums[l++], nums[r--]});
while (l < r && nums[l] == nums[l - 1])
++l;
while (l < r && nums[r] == nums[r + 1])
--r;
} else if (sum < 0) {
++l;
} else {
--r;
}
}
}
return ans;
}
};
3Sum Leetcode Solutions in Java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums.length < 3)
return new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i + 2 < nums.length; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
// Choose nums[i] as the first num in the triplet,
// and search the remaining nums in [i + 1, n - 1]
int l = i + 1;
int r = nums.length - 1;
while (l < r) {
final int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
ans.add(Arrays.asList(nums[i], nums[l++], nums[r--]));
while (l < r && nums[l] == nums[l - 1])
++l;
while (l < r && nums[r] == nums[r + 1])
--r;
} else if (sum < 0) {
++l;
} else {
--r;
}
}
}
return ans;
}
}
Note: This problem 3Sum is generated by Leetcode but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.
Next: 3Sum Closest Leetcode Solution
