3Sum - C++ Solution

1. Introduction

In this post, we tackle a popular problem in array processing and searching algorithms, known as the 3Sum problem. The goal is to find three numbers in an unsorted array that sum up to zero.

Problem

Given an unsorted integer array, find any triplet in it that sums to zero. The solution should be able to handle cases where no such triplet exists, as well as scenarios with multiple valid triplets.

2. Solution Steps

1. Sort the array to facilitate a two-pointer approach.

2. Iterate through the array, using each element as a potential starting point for the triplet.

3. For each element, use two pointers to scan the remaining part of the array for a pair that sums to the negative of the current element.

4. Skip duplicate elements to avoid repeating the same triplet.

5. Return any one triplet that sums to zero, or an empty array if none exists.

3. Code Program

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

vector<int> find3Sum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size() - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates

        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) return {nums[i], nums[left], nums[right]};

            if (sum < 0) left++;
            else right--;
        }
    }
    return {};
}

int main() {
    vector<int> nums = {4, -1, 1, 2, -1};
    vector<int> result = find3Sum(nums);

    // Output the result
    if (!result.empty()) {
        cout << "Triplet: ";
        for (int num : result) {
            cout << num << " ";
        }
        cout << endl;
    } else {
        cout << "No triplet with zero sum found." << endl;
    }

    return 0;
}

Output:

Triplet: -1 2 -1

Explanation:

The function find3Sum finds a triplet in the array that sums to zero. It first sorts the array to use a two-pointer approach. It iterates through the array, using a two-pointer technique to find two additional numbers that make the total sum zero. The solution is efficient and avoids duplicates by skipping over repeated elements. For the input array [4, -1, 1, 2, -1], it finds one of the possible triplets: [-1, 2, -1].