3Sum Problem and Solution

1. Introduction

A comprehensive guide to solving the "3Sum" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "3Sum" problem involves finding all unique triplets in an array that sum up to zero. It's a common problem that tests an understanding of array manipulation and two-pointer techniques.

2. Problem

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

3. Solution in C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (int i = 0; i < nums.size() && nums[i] <= 0; ++i)
        if (i == 0 || nums[i - 1] != nums[i]) {
            int lo = i + 1, hi = nums.size() - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum < 0) {
                    ++lo;
                } else if (sum > 0) {
                    --hi;
                } else {
                    res.push_back({ nums[i], nums[lo++], nums[hi--] });
                    while (lo < hi && nums[lo] == nums[lo - 1])
                        ++lo;
                }
            }
        }
    return res;
}

// Example usage
int main() {
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    auto triplets = threeSum(nums);
    for (const auto& triplet : triplets) {
        for (int num : triplet) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

-1 -1 2
-1 0 1

Explanation:

1. threeSum in C++ first sorts the array.

2. It uses a two-pointer technique to find triplets that sum to zero.

3. Iterates through the array, fixing one number and finding the other two using the two-pointer approach.

4. Ensures that duplicates are not counted.

4. Solution in Java

import java.util.*;

public class ThreeSum {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length && nums[i] <= 0; ++i)
            if (i == 0 || nums[i - 1] != nums[i]) {
                int lo = i + 1, hi = nums.length - 1;
                while (lo < hi) {
                    int sum = nums[i] + nums[lo] + nums[hi];
                    if (sum < 0) {
                        ++lo;
                    } else if (sum > 0) {
                        --hi;
                    } else {
                        res.add(Arrays.asList(nums[i], nums[lo++], nums[hi--]));
                        while (lo < hi && nums[lo] == nums[lo - 1])
                            ++lo;
                    }
                }
            }
        return res;
    }

    // Example usage
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> triplets = threeSum(nums);
        for (List<Integer> triplet : triplets) {
            System.out.println(triplet);
        }
    }
}

Output:

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

Explanation:

1. Java's threeSum also sorts the array first.

2. Uses a similar two-pointer technique to find the triplets.

3. Iterates through the array, avoiding duplicates, and finds pairs that sum up to the negative of the current element.

4. The result is a list of lists containing the triplets.

5. Solution in Python

def three_sum(nums):
    nums.sort()
    res = []
    for i, a in enumerate(nums):
        if i > 0 and a == nums[i - 1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            three_sum = a + nums[l] + nums[r]
            if three_sum > 0:
                r -= 1
            elif three_sum < 0:
                l += 1
            else:
                res.append([a, nums[l], nums[r]])
                l += 1
                while nums[l] == nums[l - 1] and l < r:
                    l += 1
    return res

# Example usage
nums = [-1, 0, 1, 2, -1, -4]
print("Triplets:", three_sum(nums))

Output:

Triplets: [[-1, -1, 2], [-1, 0, 1]]

Explanation:

1. Python's three_sum function sorts the list first.

2. It uses a loop combined with the two-pointer technique to find the triplets.

3. Avoids duplicates and checks sums of three numbers.

4. Appends valid triplets to the result list.