3Sum

class Solution {
public:
    vector<vector<int>> findThreeSum(vector<int>& nums) {
        set<vector<int>> resultSet;
        unordered_set<int> duplicateSet;
        unordered_map<int, int> indexMap;
        for (int i = 0; i < nums.size(); ++i)
            if (duplicateSet.insert(nums[i]).second) {
                for (int j = i + 1; j < nums.size(); ++j) {
                    int needed = -nums[i] - nums[j];
                    auto it = indexMap.find(needed);
                    if (it != indexMap.end() && it->second == i) {
                        vector<int> triple = {nums[i], nums[j], needed};
                        sort(triple.begin(), triple.end());
                        resultSet.insert(triple);
                    }
                    indexMap[nums[j]] = i;
                }
            }
        return vector<vector<int>>(resultSet.begin(), resultSet.end());
    }
};

The provided solution in C++ addresses the problem of finding all unique triplets in an array whose sum equals zero. This program defines a class named Solution with a method findThreeSum that accepts an integer vector nums and returns a vector of integer vectors.

• Start by creating a set named resultSet to store the unique triplets and an unordered_set named duplicateSet to track duplicates in the array.
• Utilize an unordered_map named indexMap to store the indices of elements for quick access and checking.
• Iterate through each element in nums using a loop indexed by i. The duplicateSet helps ensure that each number is processed only once as the main element of the triplet.
• For each unique number, use a nested loop indexed by j, starting from i + 1, to try finding the two other numbers that form a valid triplet.
• Calculate the third required number as needed = -nums[i] - nums[j] to make the sum zero.
• Use indexMap to find if the third number has been seen before, and check whether it was associated with the current index i.
• If the conditions are met, meaning the triplet sums to zero, normalize the triplet by sorting and then add it to resultSet.
• After all pairs are processed, convert resultSet to a vector before returning to ensure no duplicates.

This technique efficiently reduces potential duplicates using sets and makes use of hashing for quick access and checking, leading to an organized and concise solution for the "3Sum" problem.

class Solution {
    public List<List<Integer>> findTriplets(int[] numbers) {
        Set<List<Integer>> result = new HashSet<>();
        Set<Integer> duplicates = new HashSet<>();
        Map<Integer, Integer> previous = new HashMap<>();
        for (int i = 0; i < numbers.length; ++i) if (duplicates.add(numbers[i])) {
            for (int j = i + 1; j < numbers.length; ++j) {
                int needed = -numbers[i] - numbers[j];
                if (previous.containsKey(needed) && previous.get(needed) == i) {
                    List<Integer> triplet = Arrays.asList(numbers[i], numbers[j], needed);
                    Collections.sort(triplet);
                    result.add(triplet);
                }
                previous.put(numbers[j], i);
            }
        }
        return new ArrayList<>(result);
    }
}

The provided Java solution is structured to resolve the "3Sum" problem, where the goal is to identify all unique triplets in an array that sum up to zero. Here's how this implementation functions effectively:

• Initialize Collections: Utilizes a Set named result to store triplet lists without duplicates. Two additional collections are employed: duplicates to track any repeated elements and avoid re-evaluation, and previous, a Map, to associate each number with its index for reference.

• Iterate with Conditions: Runs a loop through the array, using a nested loop to find pairs that could form a viable triplet with the current element. This only proceeds if the current element hasn't been evaluated before, ensuring this by checking its presence in the duplicates set.

• Calculate and Find Needed Values: Inside the nested loop, calculates the required third element (named needed) that would make the sum of the triplet zero. Checks if this needed element has previously appeared at the correct position (right after the first element of the triplet) using the previous map.

• Store and Return Results: If a valid triplet is found, it is sorted to ensure order consistency, then added to the result set. This prevents duplicate triplets of different orders. Finally, the stored triplets are returned as a new list.

This solution is efficient with its use of data structures to manage checks and storage, and ensures that the output is a list of unique triplets that meet the required sum condition, skillfully combining iterative checks with hash-based data structures for effective search and storage operations.

typedef struct {
    int key;
    int value;
    UT_hash_handle hash_handle;
} MapItem;
int sort_compare(const void* p1, const void* p2) { return *(int*)p1 - *(int*)p2; }
int** findThreeSum(int* elements, int size, int* count,
                   int** colSizes) {
    MapItem* hashmap = NULL;
    qsort(elements, size, sizeof(int), sort_compare);
    int** triplets = (int**)malloc(size * size * sizeof(int*));
    *count = 0;
    *colSizes = (int*)malloc(size * size * sizeof(int));
    for (int i = 0; i < size - 2; ++i) {
        if (i > 0 && elements[i] == elements[i - 1]) continue;
        int left = i + 1, right = size - 1;
        MapItem* current;
        while (left < right) {
            int currentSum = elements[i] + elements[left] + elements[right];
            if (currentSum < 0) {
                ++left;
            } else if (currentSum > 0) {
                --right;
            } else {
                int* currentTriplet = (int*)malloc(3 * sizeof(int));
                currentTriplet[0] = elements[i];
                currentTriplet[1] = elements[left];
                currentTriplet[2] = elements[right];
                triplets[*count] = currentTriplet;
                (*colSizes)[*count] = 3;
                ++(*count);
                while (left < right && elements[left] == elements[left + 1]) ++left;
                while (left < right && elements[right] == elements[right - 1]) --right;
                ++left;
                --right;
            }
        }
    }
    return triplets;
}

The provided C code implements a solution for finding all unique triplets in an array that sum up to zero. This is commonly known as the "3Sum" problem.

Follow these steps in the code:

1. Define a structure MapItem used for creating a hash map, but in this particular implementation, Hash handles are defined but not utilized.
2. Define a function sort_compare for comparison, which is used by the quicksort function to order the array elements.
3. The function findThreeSum begins by sorting the input array using qsort.
4. The function initializes variables for dynamic memory allocation to store the result triplets and their sizes (triplets and colSizes).
5. A for-loop iterates through the array, ensuring no duplicate triplets are added by skipping equal consecutive elements.
6. Within the for-loop, a while-loop with two pointers (left and right) identifies potential triplets. These pointers adjust based on the sum comparison to zero:
   • If the sum is less than zero, the left pointer is incremented.
   • If the sum is more than zero, the right pointer is decremented.
   • If the sum is zero, a suitable triplet is found and stored in the dynamically allocated triplets array. Then both pointers are moved to skip any duplicate elements immediately succeeding them.
7. Finally, the function returns the array triplets, containing all found triplets, and colSizes reflecting the size of each triplet sub-array.

The resulting function efficiently locates all triplets that sum to zero by incorporating sorting and a two-pointer technique to reduce the complexity compared to brute-force solutions.

var threeSumUnique = function (arr) {
    const triples = new Set();
    const processed = new Set();
    const found = new Map();
    for (let p = 0; p < arr.length; ++p)
        if (!processed.has(arr[p])) {
            processed.add(arr[p]);
            for (let q = p + 1; q < arr.length; ++q) {
                let comp = -arr[p] - arr[q];
                if (found.has(comp) && found.get(comp) === p) {
                    let triplet = [arr[p], arr[q], comp].sort((x, y) => x - y);
                    triples.add(JSON.stringify(triplet));
                }
                found.set(arr[q], p);
            }
        }
    return Array.from(triples, el => JSON.parse(el));
};

The JavaScript solution implements a threeSumUnique function that identifies all unique triplets in an array which sum up to zero. The function employs a combination of data structures to efficiently track and search for necessary components to form these triples. Here is an overview of how the function effectively manages complexity and ensures uniqueness in its results:

• Initializes two collections, triples and processed, and a Map called found.
• Uses triples, a Set data structure, to store the resulting triplets in a way that automatically avoids duplicates since sets in JavaScript do not allow repeated values.
• Iterates through each element in the array using a for-loop. For each element not already processed, adds it to the processed set to prevent reconsideration in subsequent iterations of the loop.
• A nested loop then looks for two other elements that complete the triplet so their sum equals zero. The completion is calculated using the negative sum of the current and the inner loop elements.
• Uses the Map found to track whether the complement of the current and inner elements was identified in the exact same outer loop cycle.
• If an appropriate triplet is found, it is added to triples set after converting it to a string to ensure uniqueness and sorted order.
• Finally, converts the JSON string values back into arrays for the output.

This method offers an efficient way to solve the problem while handling the triplet uniqueness requirement effectively by using the combination of Set and Map structures and taking advantage of JSON for temporarily storing complex objects. Ensure your input array is well-formed and consists of integers to correctly utilize this function.

class Solution:
    def threeSum_unique(self, numbers: List[int]) -> List[List[int]]:
        result, duplicates = set(), set()
        observed = {}
        for index, value1 in enumerate(numbers):
            if value1 not in duplicates:
                duplicates.add(value1)
                for k, value2 in enumerate(numbers[index + 1:]):
                    comp = -value1 - value2
                    if comp in observed and observed[comp] == index:
                        result.add(tuple(sorted((value1, value2, comp))))
                    observed[value2] = index
        return [list(t) for t in result]

The provided Python3 solution targets the problem of finding all unique triplets in an array of integers that sum up to zero. The approach involves:

• Using a set called result to store unique triplets and another set called duplicates to track numbers already processed to avoid duplicate triplets.
• An observed dictionary maps each number to its index, ensuring that components of the triplet are identified correctly without revisiting elements.
• Iterate over the numbers array with two nested loops:
  • The outer loop selects an element value1 only if it hasn't been processed before (checked using the duplicates set).
  • The inner loop then tests possible combinations with value1 by looking for a third number comp (computed as the negative sum of value1 and value2) that has been mapped to the current index in observed.
  • If a valid comp is found within the observed dictionary at the correct index, it confirms a unique triplet which is then added to the result set.

The key points in this solution include:

• Use of set data structures to ensure all triplets are unique and to handle the inherent uniqueness requirement efficiently.
• Efficient handling of indices and values using dictionaries to minimize unnecessary calculations and lookups.

Finally, the list of triplets stored as tuples in the result set is converted back to a list of lists before returning, complying with the expected output format. This method efficiently minimizes redundant processing and avoids overcounting while allowing for an intuitive triplet-building logic using hash maps.