15. 3Sum

Summary

Solution Approach	Explanation	Time Complexity	Space Complexity
Brute Force	Iterate through all triplets and check if their sum is zero. This approach is straightforward but inefficient for large arrays.	\(O(n^3)\) - three nested loops iterate through the array	\(O(1)\) - no extra space used beyond input storage
Two Pointers	Sort the array first, then for each element, use two pointers from both ends to find pairs that sum to the target. Skip duplicates to avoid redundant triplets.	\(O(n^2)\) - outer loop iterates \(n\) times, inner two-pointer search takes \(O(n)\)	\(O(1)\) - only uses constant extra space for pointers and variables
HashSet without Sorting	Convert 3Sum to 2Sum for each element. Use sets for deduplication and avoid processing duplicate first elements. No array modification required.	\(O(n^2)\) - outer loop iterates \(n\) times, inner 2Sum takes \(O(n)\)	\(O(n)\) - uses sets for storing seen elements and results

Implementation

Python

# HashSet without Sorting
def two_sum(nums: List[int], target: int, result: List[List[int]]) -> List[List[int]]:
    seen = set()
    for j in range(len(nums)):
        complement = target - nums[j]
        if complement in seen:
            t = tuple(sorted(
                [-target, nums[j], complement]
            ))
            result.add(t)
        seen.add(nums[j])

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        seen = set()
        result = set()
        for i in range(len(nums)-2):
            target = -nums[i]
            if nums[i] not in seen:
                two_sum(
                    nums=nums[i+1:],
                    target=target,
                    result=result
                )
                seen.add(nums[i])
        return list(result)