Problem Statement

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


Solution Explanation

Given an integer array like below,

    [-1, 0, 1, 2, -1, -4],

The solution would like below,

 [
  [-1, 0, 1],
  [-1, -1, 2]
 ]

The brute force would be to have 3 loops, sum all kinds of combinations and see if they add up to 0.

To optimize it, we can sort the array, have 2 loops, compare the first elements with the last and increase or decrease the counter depending on how close the sum is to 0.

Below is the java implementation of Three Sum(3sum) looks like,

class ThreeSum {

	public static void main(String[] args) {
		int[] tarr = { -1, 0, 1, 2, -1, -4 };
		System.out.println(threeSum(tarr));

	}

	public static List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> result = new LinkedList<>();
		int sum = 0, temp = 0;
		Arrays.sort(nums);
		for (int i = 0; i < nums.length - 2; i++) {
			if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
				sum = 0 - nums[i];
				int x = i + 1, y = nums.length - 1;
				while (x < y) {
					if (nums[x] + nums[y] == sum) {
						result.add(Arrays.asList(nums[x], nums[y], nums[i]));
						while (x < y && nums[x] == nums[x + 1])
							x++;
						while (x < y && nums[y] == nums[y - 1])
							y--;
						x++;
						y--;
					} else if (nums[x] + nums[y] < sum) {
						x++;
					} else
						y--;

				}
			}
		}

		return result;

	}
}
Time Complexity

The time complexity is O(n^2).