LeetCode Python/Java/C++/JS  >  Hash Table  >  15. 3Sum  >  Solved in Python, Ruby, Go, C++, JavaScript, C#, Java  >  GitHub or Repost

    LeetCode link: 15. 3Sum, difficulty: Medium.

    Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

    Notice that the solution set must not contain duplicate triplets.

    Example 1:

    Input: nums = [-1,0,1,2,-1,-4]

    Output: [[-1,-1,2],[-1,0,1]]

    Explanation:

    nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
    nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
    nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
    The distinct triplets are [-1,0,1] and [-1,-1,2].
    Notice that the order of the output and the order of the triplets does not matter.

    Example 2:

    Input: nums = [0,1,1]

    Output: []

    Explanation:

    The only possible triplet does not sum up to 0.

    Example 3:

    Input: nums = [0,0,0]

    Output: [[0,0,0]]

    Explanation: The only possible triplet sums up to 0.

    Constraints:

    • 3 <= nums.length <= 3000
    • -10^5 <= nums[i] <= 10^5
    Hint 1

    So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!

    Hint 2

    For the two-sum problem, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

    Hint 3

    The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

    Intuition
    PreviousNext

    Webmaster (Zhang Jian): ๐Ÿ‘‹

    Hi everyone! I am Zhang Jian.
    I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed leader.me!

    ๐Ÿš€ leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.

    Build your programmer brand at leader.me โ†’


    1. The sum of three numbers equals 0, which is equivalent to the sum of two numbers equaling the negative third number.
    2. There are two options:
      • Option 1. First determine one number, and then find the other two numbers.
      • Option 2. First determine two numbers, and then find the third number.
    3. If you choose option 2, you need to use Map. Because you need to deduplicate nums; when searching for the third number in Map, you also need to avoid the two numbers that have been determined, which is more troublesome to implement.
    4. If you choose option 1, you need to use the two pointers algorithm when searching for the other two numbers.
    5. For option 2, only the Python sample code is given. This article focuses on option 1.

    Step-by-Step Solution

    1. Sort nums.
    2. Iterate over nums.

    3. pseudocode:

      for (i = 0; i < nums.length; i++) {
   left = i + 1
   right = nums.length - 1

   while (left < right) {
      if (condition1) {
         left += 1
      } else (condition2) {
         right -= 1
      }
   }
}

    Complexity

    Time complexity

    O(N * N)

    Space complexity

    O(N)

    Solution in languages: Python Ruby Go C++ JavaScript C# Java

    Python # 

    # If you want the program to run faster, uncomment the two places in the code. 
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        # nums_2 = []
        # for i, num in enumerate(nums):
        #     if i >= 3 and num == nums[i - 1] == nums[i - 2] == nums[i - 3]:
        #         continue
        #     nums_2.append(num)
        # nums = nums_2
        results = set()

        for i, num in enumerate(nums[:len(nums) - 2]):
            # if num > 0:
            #     break
            left = i + 1
            right = len(nums) - 1

            while left < right:
                sum_ = nums[left] + nums[right]
                if sum_ == -num:
                    results.add((num, nums[left], nums[right]))
                    left += 1
                elif sum_ > -num:
                    right -= 1
                else:
                    left += 1

        return list(results)

    Ruby # 

    # @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
  nums.sort!
  results = Set.new

  nums_2 = []
  nums.each_with_index do |num, i|
    next if i >= 3 && num == nums[i - 1] && num == nums[i - 2] && num == nums[i - 3]
    nums_2.append(num)
  end

  nums = nums_2

  # Iterate through each number as potential first element
  (0...nums.length - 2).each do |i|
    break if nums[i] > 0

    left = i + 1
    right = nums.length - 1

    # Two-pointer approach for remaining elements
    while left < right
      current_sum = nums[i] + nums[left] + nums[right]
      if current_sum == 0
        # Add sorted triplet to avoid duplicates
        results.add([nums[i], nums[left], nums[right]])
        left += 1
        right -= 1
      elsif current_sum < 0
        left += 1 # Need larger sum
      else
        right -= 1 # Need smaller sum
      end
    end
  end

  results.to_a
end

    Go # 

    func threeSum(nums []int) [][]int {
    sort.Ints(nums)

    nums2 := make([]int, 0)
    for i, num := range nums {
        if i >= 3 && num == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] {
            continue
        }
        nums2 = append(nums2, num)
    }

    nums = nums2
    results := make([][]int, 0)
    seen := make(map[string]bool)

    for i := 0; i < len(nums)-2; i++ {
        // if nums[i] > 0 {
        //     break
        // }

        left := i + 1
        right := len(nums) - 1

        for left < right {
            sum := nums[left] + nums[right]
            if sum == -nums[i] {
                triplet := []int{nums[i], nums[left], nums[right]}
                key := fmt.Sprintf("%d,%d,%d", triplet[0], triplet[1], triplet[2])
                if !seen[key] {
                    results = append(results, triplet)
                    seen[key] = true
                }
                left++
            } else if sum > -nums[i] {
                right--
            } else {
                left++
            }
        }
    }

    return results
}

    C++ # 

    class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        // Uncomment to speed up
        // vector<int> nums2;
        // for (int i = 0; i < nums.size(); i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] &&
        //     nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.push_back(nums[i]);
        // }
        // nums = nums2;

        vector<vector<int>> results;
        set<vector<int>> seen;

        for (int i = 0; i < nums.size() - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.size() - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum == -nums[i]) {
                    vector<int> triplet = {nums[i], nums[left], nums[right]};

                    if (seen.find(triplet) == seen.end()) {
                        results.push_back(triplet);
                        seen.insert(triplet);
                    }

                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return results;
    }
};

    JavaScript # 

    /**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) => a - b);

    // Uncomment to speed up
    // let nums2 = [];
    // for (let i = 0; i < nums.length; i++) {
    //     if (i >= 3 && nums[i] === nums[i-1] && nums[i-1] === nums[i-2] && nums[i-2] === nums[i-3]) {
    //         continue;
    //     }
    //     nums2.push(nums[i]);
    // }
    // nums = nums2;

    const results = [];
    const seen = new Set();

    for (let i = 0; i < nums.length - 2; i++) {
        // Uncomment to speed up
        // if (nums[i] > 0) {
        //     break;
        // }
        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const sum = nums[left] + nums[right];

            if (sum === -nums[i]) {
                const triplet = [nums[i], nums[left], nums[right]];
                const key = triplet.join(',');
                if (!seen.has(key)) {
                    results.push(triplet);
                    seen.add(key);
                }
                left++;
            } else if (sum > -nums[i]) {
                right--;
            } else {
                left++;
            }
        }
    }

    return results;
};

    C# # 

    public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);

        // Uncomment to speed up
        // var nums2 = new List<int>();
        // for (int i = 0; i < nums.Length; i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.Add(nums[i]);
        // }
        // nums = nums2.ToArray();

        var results = new List<IList<int>>();
        var seen = new HashSet<string>();

        for (int i = 0; i < nums.Length - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.Length - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == -nums[i]) {
                    var triplet = new List<int> { nums[i], nums[left], nums[right] };
                    string key = string.Join(",", triplet);
                    if (!seen.Contains(key)) {
                        results.Add(triplet);
                        seen.Add(key);
                    }
                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return results;
    }
}

    Java # 

    class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        // Uncomment to speed up
        // List<Integer> nums2 = new ArrayList<>();
        // for (int i = 0; i < nums.length; i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.add(nums[i]);
        // }
        // nums = nums2.stream().mapToInt(i -> i).toArray();

        List<List<Integer>> results = new ArrayList<>();
        var seen = new HashSet<>();

        for (int i = 0; i < nums.length - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == -nums[i]) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[left], nums[right]);
                    if (!seen.contains(triplet)) {
                        results.add(triplet);
                        seen.add(triplet);
                    }
                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return results;
    }
}
    Solution in languages: Python Ruby Go C++ JavaScript C# Java

    Other languages

    Welcome to contribute code to LeetCode.blog GitHub -> 15. 3Sum. Thanks!

    Level Up Your Developer Identity

    ๐Ÿš€ While mastering algorithms is key, showcasing your talent is what gets you hired.
    We recommend leader.me โ€” the ultimate all-in-one personal branding platform for programmers.

    The All-In-One Career Powerhouse:

    • ๐Ÿ“„ Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
    • ๐ŸŒ Free Custom Domain: Bind your own personal domain for freeโ€”forever.
    • โœจ Premium Subdomains: Stand out with elite tech handle like name.leader.me.

    Build Your Programmer Brand at leader.me โ†’

    Intuition of solution 2: Use Map (complex and slow)

    Webmaster (Zhang Jian): ๐Ÿ‘‹

    Hi everyone! I am Zhang Jian.
    I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed leader.me!

    ๐Ÿš€ leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.

    Build your programmer brand at leader.me โ†’


    Please refer to the idea of โ€‹โ€‹โ€‹โ€‹Solution 1. Here we only give the code to explain why using Map is not a good idea.

    Complexity

    Time complexity

    O(N * N)

    Space complexity

    O(N)

    Python # 

    # from collections import defaultdict

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = duplicate_removed_nums(nums)

        results = set()
        num_to_indices = defaultdict(list)

        for i, num in enumerate(nums):
            num_to_indices[num].append(i)

        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if -(nums[i] + nums[j]) in num_to_indices:
                    for index in num_to_indices[-(nums[i] + nums[j])]:
                        if index not in (i, j):
                            result = [nums[i], nums[j], nums[index]]
                            result.sort()
                            results.add(tuple(result))

        return list(results)


def duplicate_removed_nums(nums):
    num_to_count = defaultdict(int)

    for i, num in enumerate(nums):
        if num_to_count[num] <= 2 or (num_to_count[num] <= 3 and num == 0):
            num_to_count[num] += 1

    new_nums = []

    for num in num_to_count:
        new_nums.extend([num] * num_to_count[num])

    return new_nums

    Other languages

    Welcome to contribute code to LeetCode.blog GitHub -> 15. 3Sum. Thanks!
    PreviousNext

    Level Up Your Developer Identity

    ๐Ÿš€ While mastering algorithms is key, showcasing your talent is what gets you hired.
    We recommend leader.me โ€” the ultimate all-in-one personal branding platform for programmers.

    The All-In-One Career Powerhouse:

    • ๐Ÿ“„ Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
    • ๐ŸŒ Free Custom Domain: Bind your own personal domain for freeโ€”forever.
    • โœจ Premium Subdomains: Stand out with elite tech handle like name.leader.me.

    Build Your Programmer Brand at leader.me โ†’