Given an integer array nums, return all the triplets

 3Sum

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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

If you want to solve the threeSum problem with a time complexity of O(n3)O(n^3)O(n3), you can use a straightforward brute-force approach. This method involves three nested loops to check all possible triplets in the array. While this approach is less efficient than the two-pointer method, it still works correctly for finding all unique triplets that sum to zero.

Swift Implementation:

Here’s the brute-force approach for the threeSum function in Swift:

func threeSum(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]]()
    let n = nums.count
    
    // Use a set to avoid duplicate triplets
    var tripletSet = Set<[Int]>()
    
    // Sort the array to help with duplicate removal
    let sortedNums = nums.sorted()
    
    for i in 0..<n {
        for j in i+1..<n {
            for k in j+1..<n {
                if sortedNums[i] + sortedNums[j] + sortedNums[k] == 0 {
                    let triplet = [sortedNums[i], sortedNums[j], sortedNums[k]]
                    tripletSet.insert(triplet)
                }
            }
        }
    }
    
    result = Array(tripletSet)
    return result
}

// Example usage:
let nums = [-1, 0, 1, 2, -1, -4]
let triplets = threeSum(nums)
print(triplets) // Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation:

1. Sorting:
   • First, sort the array to help with duplicate removal later.
2. Three Nested Loops:
   • Use three nested loops to iterate through all possible triplets in the array.
   • The outer loop runs from 0 to n-1.
   • The middle loop runs from i+1 to n-1.
   • The inner loop runs from j+1 to n-1.
3. Check for Sum:
   • For each triplet (sortedNums[i], sortedNums[j], sortedNums[k]), check if their sum is zero.
   • If the sum is zero, add the triplet to a set to avoid duplicates.
4. Convert Set to Array:
   • Convert the set of triplets back to an array and return it as the result.

Time Complexity:

• This approach has a time complexity of O(n3)O(n^3)O(n3) due to the three nested loops.

Example:

For the input [-1, 0, 1, 2, -1, -4], the output will be:

[[-1, -1, 2], [-1, 0, 1]]

2 Solution

To solve the problem of finding all unique triplets in an array that sum up to zero, we can use a sorted array and a two-pointer technique. This approach ensures that we efficiently find the triplets without duplicates. Here’s a detailed step-by-step solution:

Approach:

1. Sort the Array:
   • Sorting helps to easily skip duplicates and efficiently use the two-pointer technique.
2. Iterate Through the Array:
   • Use a for loop to fix the first element of the triplet.
3. Two-Pointer Technique:
   • For each fixed element, use two pointers to find pairs that sum up to the negative value of the fixed element.
4. Skip Duplicates:
   • Ensure that the solution does not include duplicate triplets by skipping identical elements during the iteration.

Implementation in Swift:

func threeSum(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]]()
    let nums = nums.sorted()
    let n = nums.count
    
    for i in 0..<n {
        if i > 0 && nums[i] == nums[i - 1] {
            continue // Skip duplicate elements
        }
        
        var left = i + 1
        var right = n - 1
        
        while left < right {
            let sum = nums[i] + nums[left] + nums[right]
            
            if sum == 0 {
                result.append([nums[i], nums[left], nums[right]])
                
                // Skip duplicates for the second and third elements
                while left < right && nums[left] == nums[left + 1] {
                    left += 1
                }
                while left < right && nums[right] == nums[right - 1] {
                    right -= 1
                }
                
                left += 1
                right -= 1
            } else if sum < 0 {
                left += 1
            } else {
                right -= 1
            }
        }
    }
    
    return result
}

// Example usage:
let nums = [-1, 0, 1, 2, -1, -4]
let triplets = threeSum(nums)
print(triplets) // Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation:

1. Sorting:
   • First, sort the array to handle duplicates and use the two-pointer technique efficiently.
2. Main Loop:
   • Iterate through the array with index i to fix the first element of the triplet.
   • Skip duplicate elements to avoid repeating the same triplet.
3. Two-Pointer Technique:
   • Initialize two pointers, left and right, for each fixed element.
   • Adjust the pointers based on the sum of the triplet:
     • If the sum is zero, add the triplet to the result and move both pointers inward, skipping duplicates.
     • If the sum is less than zero, move the left pointer to the right to increase the sum.
     • If the sum is greater than zero, move the right pointer to the left to decrease the sum.
4. Result:
   • The result array contains all unique triplets that sum up to zero.

Time Complexity:

• The time complexity is O(n2)O(n^2)O(n2) because we iterate through the array and use two pointers for each element. Sorting the array takes O(nlog⁡n)O(n \log n)O(nlogn).

func threeSum(_ nums: [Int]) -> [[Int]] {
        let sortedNums = nums.sorted()
        var triplets: Set<[Int]> = []
        
        for i in 0..<sortedNums.count {
            var j = i + 1
            var k = sortedNums.count - 1
            
            while j < k {
                let sum = sortedNums[i] + sortedNums[j] + sortedNums[k]
                
                if sum == 0 { triplets.insert([sortedNums[i], sortedNums[j], sortedNums[k]]) }
                
                if sum <= 0 { j += 1 }
                if sum >= 0 { k -= 1 }
            }
        }
        
        return Array(triplets)
    }