15.3sum.md

15. 3Sum

3 Pointers

We can brute force to find all possible triplets, but it will generate duplicate triplets and also lead to bad time complexity O(n^3).

We can sort the array first which allows us efficiently avoid duplicates and leverage two pointers techniques. Sorted array group duplicate together, so we can skip the duplicate elements easily by checking nums[i - 1] == nums[i], ensuring that each triplet is unique.

The core idea behiding avoiding duplicates is to ensure that the tripulates (a, b, c) we iterate follow a ascending order, i.e., a <= b <= c, while permutations like (b, a, c) or (c, b, a) can be avoided. For example, after sorting, the triplet (-1, 0, 1) will be correctly enumerated, while permutations like (0, -1, 1) or (1, 0, -1) will not be considered.

排序能讓我們「定義唯一的順序」，方便去除重複。給定三個數 a, b, c 有不同的排列方式，如果我們沒有排序，很難判斷 (a, b, c) vs (b, c, a) 是不是同一組，排序過後使得 a <= b <= c，這樣我們就只會找到唯一的從小到大的 (a, b, c)，這樣所有組合的輸出就會是固定順序，也很容易判斷重複。

Sort array [-1, 0, 1, 2, -1, -4] becomes [-4, -1, -1, 0, 1, 2], then we can fix the 1st number one by one, and use two points approach to find the 2nd + 3rd number that make the three sum is equal to zero. (the same idea t0 167. Two Sum II - Input Array Is Sorted)

You can skip this part if you are familiar with 167. Two Sum II - Input Array Is Sorted.

# Iterate the first element as 1st number
[-4, -1, -1, 0, 1, 2]
[1st]
     -1, -1, 0, 1, 2
    [2nd]        [3rd]
       ->        <-

# Iterate the second element as 1st number
[-4, -1, -1, 0, 1, 2]
    [1st]
         -1, 0, 1, 2
        [2nd]    [3rd]
            ->   <-

The first number sets to -4, the target number will be 4, then we apply two points approach to the subarray [-1, -1, 0, 1, 2] to find the 2nd + 3rd numbers, when left + right < target, we move forward left pointer, otherwise, move backward right pointer.

if (nums[left]+nums[right]==sum)
{
    记录结果;
    left++;
    right--;
    while (left<right && nums[left]==nums[left-1]) left++;
    while (left<right && nums[right]==nums[right+1]) right--;
}

def threeSum(nums):
    nums.sort()
    n = len(nums)
    triplets = []
    
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # Skip duplicate elements
        
        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:
                triplets.append([nums[i], nums[left], nums[right]])
                # Skip duplicate elements
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                right -= 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    
    return triplets

fun threeSum(nums: IntArray): List<List<Int>> {
    nums.sort()
    val results = mutableListOf<List<Int>>()
    for (i in 0 until nums.size) {
        val first = nums[i]

        // For sorted array, when we encounter the first positive, that means the number after will be positive as well. We can't find sum == 0 for two numbers are positive anymore.
        if (0 < first) break

        // Skip duplicate for the first number
        if (0 < i && nums[i] == nums[i - 1]) continue

        var left = i + 1
        var right = nums.size - 1
        val target = -first
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                results.add(listOf(first, nums[left], nums[right]))

                // Skip the duplicate numbers
                do {
                    left++
                } while (left < nums.size && nums[left] == nums[left - 1]) // Or we can check `left < right` only
                do {
                    right--
                } while (0 <= right && nums[right] == nums[right + 1]) // Or we can check `left < right` only
            } 
            // Two sum is less than target, means negative number is too negative, move forward left pointer to "smaller" negative number
            else if (nums[left] + nums[right] < target) {
                do {
                    left++
                } while (left < nums.size && nums[left] == nums[left - 1])
            } else {
                do {
                    right--
                } while (0 <= right && nums[right] == nums[right + 1])
            }
        }
    }
    return results
}

• Time Complexity: O(n^2) for two iterations.
• Space Complexity: O(log n) for sorting.