# LeetCode 15. 3Sum

## Description

https://leetcode.com/problems/3sum/description/

Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

```For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
```

## Explanation

Three sum is a follow-up question for two sum.

For three sum, we are going to find all possible triplets which each of the triplets meets following criteria:

num1 + num2  + num3 = 0

Just by making some modifications to equation, num1 + num2 = -num2. This is same as the two sum problem: num1 + num2 = target.

So for each number in the input array, we can use two sum approach to find whether there are two numbers in the rest of array add up together equal to the negative value of the number.

## Java Solution

```class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> results = new ArrayList<>();

if (nums == null || nums.length < 3) {
return results;
}

Arrays.sort(nums);

for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}

int target = -nums[i];
int left = i + 1;
int right = nums.length - 1;

twoSumHelper(nums, results, target, left, right);
}

return results;
}

private void twoSumHelper(int[] nums, List<List<Integer>> results, int target, int left, int right) {
while (left < right) {
if (nums[left] + nums[right] == target) {
List<Integer> triplet = new ArrayList<>();

left++;
right--;

while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (nums[left] + nums[right] > target) {
right--;
} else if (nums[left] + nums[right] < target) {
left++;
}
}
}
}```

## 4 Thoughts to “LeetCode 15. 3Sum”

1. NK007 says:

This program returns duplicate triplets as well. Do you think we should have an additional method for checking the duplicates?

2. GH0S7 says:

Is the Time Complexity O(n^2) ?

3. williamwangzn says:

The way to solve the problem is clearly.

1. GoodTecher says:

Thank you 🙂