3Sum

Intuition

Once the values are sorted, a pair that sums to a needed target can be located by moving two pointers inward: if the running sum is too small we advance the left pointer to gain value, and if it is too large we pull the right pointer back to lose value. Fixing the first number turns the three-number search into many two-number searches, and sorting also makes it trivial to skip repeated values so no duplicate triplet is ever emitted.

Algorithm walkthrough

1. 1Sort the array in ascending order so pointer movement predictably increases or decreases the sum.
2. 2Iterate an index i as the first element, skipping it when it equals the previous element to avoid repeats.
3. 3Set left = i + 1 and right = end, then compute the three-way sum at each step.
4. 4If the sum is negative move left rightward, if positive move right leftward, and if zero record the triplet.
5. 5After recording, advance both pointers past any equal neighbors to keep the results unique.

Implementation

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        n = len(nums)
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] > 0:
                break
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    res.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
        return res