The Three Sum problem on LeetCode is a well-known algorithmic problem that asks you to find all unique triplets in an array of integers that sum up to a specific target value. In other words, given an array of numbers, the task is to find all combinations of three numbers from the array such that their sum equals a given target value.
Problem Statement: Given an array nums of n integers, find all unique triplets (a, b, c) in the array such that a + b + c = 0. The solution set must not contain duplicate triplets.
Solving this problem typically involves writing an efficient algorithm that avoids duplicates and has a time complexity better than O(n^3). A common approach is to sort the array and use two-pointer techniques to find the triplets efficiently.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums, int target) {
vector<vector<int>> result; // to store the final answer
sort(nums.begin(), nums.end()); // sort the array in ascending order
int n = nums.size(); // get the size of the array
for (int i = 0; i < n - 2; i++) { // loop through the array from 0 to n-3
if (i > 0 && nums[i] == nums[i-1]) continue; // skip duplicates for the first element
int left = i + 1; // set the left pointer to i+1
int right = n - 1; // set the right pointer to n-1
while (left < right) { // loop until left and right pointers meet
int sum = nums[i] + nums[left] + nums[right]; // calculate the sum of the triplet
if (sum == target) { // if the sum is equal to the target
result.push_back({nums[i], nums[left], nums[right]}); // add the triplet to the result
left++; // move the left pointer to the right
right--; // move the right pointer to the left
while (left < right && nums[left] == nums[left-1]) left++; // skip duplicates for the second element
while (left < right && nums[right] == nums[right+1]) right--; // skip duplicates for the third element
} else if (sum < target) { // if the sum is less than the target
left++; // move the left pointer to the right
} else { // if the sum is greater than the target
right--; // move the right pointer to the left
}
}
}
return result; // return the final answer
}
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4}; // sample input array
int target = 0; // sample target value
vector<vector<int>> ans = threeSum(nums, target); // call the function with input array and target value
for (auto v : ans) { // loop through the result vector
for (auto x : v) { // loop through each triplet vector
cout << x << " "; // print each element of the triplet
}
cout << endl; // print a new line after each triplet
}
return 0;
}
// Output:
// -1 -1 2
// -1 0 1 The algorithm runs in quadratic time, O(n^2), where n is the number of elements in the input array. This is mainly due to the two-pointer technique.
The space used by the algorithm is also quadratic, O(n^2), primarily because of the storage required for the result vector, which can hold up to O(n^2) triplets in the worst case.