15. 3Sum

Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Solution: Sort + Two Pointers

This solution leverages sorting and the two-pointer technique for an efficient approach.

Algorithm:

1. Sort the array: Sorting allows us to easily skip duplicate numbers and efficiently manage the two pointers. We sort nums in ascending order.

2. Iterate and find triplets: We iterate through the sorted array using a primary index i. For each nums[i]:

   • We skip if nums[i] is positive (since the sum must be 0 and the array is sorted).
   • We skip if nums[i] is the same as the previous element (to avoid duplicate triplets).
   • We initialize two pointers, j (starting at i + 1) and k (starting at the end of the array).
   • We calculate the sum x = nums[i] + nums[j] + nums[k].
   • If x < 0: Increase j to include a larger number.
   • If x > 0: Decrease k to include a smaller number.
   • If x == 0: We found a triplet! Add it to the result ans. Then, increment j and decrement k. We also handle duplicates by skipping consecutive identical elements at j and k.

3. Return the result: The ans array will contain all unique triplets that sum to 0.

Time Complexity: O(n^2), dominated by the nested loops. The sorting step is O(n log n), but it's asymptotically less significant than the nested loops.

Space Complexity: O(log n) in the average case for sorting (depends on the sorting algorithm used), and O(m) in the worst case to store the resulting triplets, where m is the number of triplets found. In most cases, m will be significantly smaller than n.

Code (Python3)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = []
        for i in range(n - 2):
            if nums[i] > 0:
                break  # Since array is sorted, no need to continue
            if i > 0 and nums[i] == nums[i - 1]:
                continue  # Skip duplicate nums[i]
 
            j, k = i + 1, n - 1
            while j < k:
                x = nums[i] + nums[j] + nums[k]
                if x < 0:
                    j += 1
                elif x > 0:
                    k -= 1
                else:
                    ans.append([nums[i], nums[j], nums[k]])
                    while j < k and nums[j] == nums[j + 1]:  # Skip duplicates
                        j += 1
                    while j < k and nums[k] == nums[k - 1]:  # Skip duplicates
                        k -= 1
                    j += 1
                    k -= 1
        return ans

The code in other languages (Java, C++, Go, TypeScript, Rust, JavaScript, C#, Ruby, PHP) follows the same algorithmic approach, just with different syntax and data structures. The core logic of sorting, iterating, using two pointers, and handling duplicates remains the same.