Given an integer array and a target value, can you write a function that returns all the triplets whose sum is equal to the target value?

Question Analysis

The question asks you to write a function that identifies all unique triplets in an integer array whose elements add up to a given target value. This problem is a variation of the "3Sum" problem, which is a classic algorithmic challenge.

Key Points to Consider:

• Input: An integer array nums and an integer target.
• Output: A list of all unique triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] = target.
• Constraints: The triplets should be unique, meaning no duplicate triplet sets in the output.

To solve this problem efficiently, sorting the array and using a two-pointer approach within a loop can be a viable strategy. This approach reduces the complexity compared to a brute force solution, which involves checking all possible combinations.

Answer

def threeSum(nums, target):
    # Sort the array to use two-pointer technique
    nums.sort()
    triplets = []
    n = len(nums)
    
    for i in range(n - 2):
        # Avoid duplicates for the first number
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Two-pointer approach
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if current_sum == target:
                triplets.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                
                # Avoid duplicates for the second and third numbers
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return triplets

# Example usage:
nums = [1, 2, -1, -1, -2, 3, 0, 4]
target = 3
print(threeSum(nums, target))

Explanation:

• Sorting: The array is first sorted to facilitate the two-pointer approach.
• Iteration: Iterate through the array up to n - 2 to fix the first element of the triplet.
• Two-Pointer Technique: For the remaining elements, use two pointers (left and right) to find pairs that complement the fixed element to achieve the target sum.
• Duplicate Avoidance: Skip duplicate elements for the first, second, and third numbers to ensure unique triplets.
• Complexity: The algorithm runs in (O(n^2)) time complexity, which is efficient given the constraints.