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.

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.

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 🙂