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.

Video Tutorial

Java Solution

4 Thoughts to “LeetCode 15. 3Sum”

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

Leave a Reply

Your email address will not be published. Required fields are marked *