15. 3Sum

Edited by Charles

Medium · Python · HashTable

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Sort the array, fix one value, and use two pointers for the remaining pair. Skip repeated values to avoid duplicate triplets.

Original study notes follow, including intermediate snippets and earlier attempts.

The solution below requires a sort on the array!

Let sort_nums[i] iterate over the whole sort_nums. Consider such exceptions:

1. sort_nums[i] is positive. Since sort_nums is listed in ascending order, the rest two will be absolutely positive. No need to search them!
2. i =1, 2, 3, …. sort_nums[i] == sort_nums[i - 1]. For example, we already add a correct subarray [-1, -1, 2] or [0, 0, 0] to the result. No need to search the rest two for -1 or 0, since all possible subarrays have been searched at the first -1 or 0.

Within each iteration, we first choose sort_nums[i], and then define two pointers, left and right, where left = i + 1 and right = n - 1. The core idea is for a chosen sort_nums[i], we search all possible combinations by moving left and right. What matters is some combinations can be skipped. Let sum_3 = sort_nums[i] + sort_nums[left] + sort_nums[right].

1. if sum_3 is positive, we change sort_nums[right] to a smaller number, since the list is sorted in ascending order.
2. similarly, sum_3 is negative, we change sort_nums[left] to a larger number.
3. if sum_3 is 0, we add this [sort_nums[i], sort_nums[left], sort_nums[right]] to the result. However, we need to avoid the incoming repetition problem.
   1. if sort_nums[right - 1] == sort_nums[right], for example, [-2, -1, 0, 1, 1, 1], now i = 0, left = 3, right = 5. No need to choose 1 for right, since the combination is a replicate of the current combination.
   2. similarly, if sort_nums[left] == sort_nums[left + 1], for example, [-1, -1, -1, 0, 0, 2], now i = 0, left = 1, right = 5. No need to choose -1 for left anymore.

Study record

Field	Value
Attempts	2
Mastery	❚❚
The Latest Attempt	January 5, 2026
Feedback	Double Pointers again! Strongly Recommended for Multiple Attempts!

Python solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        sort_nums = sorted(nums)
        n = len(nums)
        result = []

        for i in range(n-2):
            if sort_nums[i] > 0:
                break

            if i > 0 and sort_nums[i] == sort_nums[i - 1]:
                continue
            left = i + 1
            right = n - 1

            while left < right:
                sum_3 = sort_nums[i] + sort_nums[left] + sort_nums[right]
                if sum_3 == 0:
                    result.append([sort_nums[i], sort_nums[left], sort_nums[right]])
                    while left < right and sort_nums[right - 1] == sort_nums[right]:
                        right -= 1
                    while left < right and sort_nums[left + 1] == sort_nums[left]:
                        left += 1

                    left += 1
                    right -= 1

                elif sum_3 > 0:
                    right -= 1
                else:
                    left += 1

        return result

---

Back to Day 6 Hash Table II · All Algorithm notes