thiagowfx's avatar

Β¬ just serendipity πŸ€ (not just serendipity)

ByteByteGo: Triplet Sum

β€’ 137 words β€’ 1 min β€’ updated

ByteByteGo: Triplet Sum:

python
from typing import List

def triplet_sum(nums: List[int]) -> List[List[int]]:
    sequence = sorted(nums)

    ans = []

    for ia, a in enumerate(sequence):
        if a > 0:  # positive numbers cannot add up to zero
            break

        if ia > 0 and sequence[ia - 1] == sequence[ia]:  # prevent duplicates
            continue

        ib = ia + 1
        ic = len(sequence) - 1

        while ib < ic:
            b = sequence[ib]
            c = sequence[ic]

            target = -a
            if (b + c) == target:
                ans.append([a, b, c])
                ib += 1
                ic -= 1

                # keep going, preventing duplicates
                while ib < ic and sequence[ib - 1] == sequence[ib]:
                    ib += 1
                while ib < ic and sequence[ic + 1] == sequence[ic]:
                    ic -= 1
            elif (b + c) < target:
                ib += 1
            else:
                ic -=1

    return ans

Time complexity: O(n^2)