3Sum Algorithm

The 3Sum algorithm is a popular solution to a computational problem that involves finding all unique triplets in a given integer array, such that the sum of the three numbers in the triplet is equal to zero. This problem is often encountered in various programming tasks and interviews, and it can be solved using different approaches, including brute force and more advanced techniques like sorting and hashing. The 3Sum algorithm is efficient and elegant, as it reduces the time complexity to O(n^2) from the O(n^3) of the brute force method. The 3Sum algorithm works by first sorting the given array of integers. Once sorted, it iteratively processes each element in the array as the first number of the potential triplet. For each element, the algorithm then initiates two pointers, one starting from the element immediately after the current one and the other starting from the end of the array. The sum of the three numbers (i.e., the current element and the two pointers' values) is compared to zero. If the sum is greater than zero, it indicates that the largest number (i.e., the end pointer) should be decreased to yield a smaller sum. Conversely, if the sum is less than zero, the smallest number (i.e., the start pointer) should be increased to yield a larger sum. As the pointers converge, if a sum of zero is found, the triplet is added to the result list. The algorithm continues until all triplets satisfying the condition are identified, and it returns the unique triplets as its final output.
class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> result;
        if (num.empty()) {
            return result;
        }
        sort(num.begin(), num.end());
        for (int start = 0; start < num.size(); start++) {
            int i = start + 1;
            int j = num.size() - 1;
            int target = -num[start];
            while (i < j) {
                if (num[i] + num[j] == target) {
                    vector<int> triple;
                    triple.push_back(num[start]);
                    triple.push_back(num[i]);
                    triple.push_back(num[j]);
                    result.push_back(triple);
                    while (i + 1 < num.size() && num[i] == num[i+1]) {
                        i++;
                    }
                    while (j - 1 >= 0 && num[j] == num[j-1]) {
                        j--;
                    }
                    i++;
                    j--;
                } else if (num[i] + num[j] < target) {
                    i++;
                } else {
                    j--;
                }
            }
            while (start + 1 < num.size() && num[start] == num[start+1]) {
                start++;
            }
        }
        return result;
    }
};

LANGUAGE:

DARK MODE: