LeetCode: 15 3Sum

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:

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation:
nums[i] + nums[j] + nums[k] == 0:
-1 + -1 + 2 = 0
-1 + 0 + 1 = 0

问题

给定一个整数数组 nums，返回所有满足 i != j、i != k 和 j != k 且 nums[i] + nums[j] + nums[k] == 0 的三元组 [nums[i], nums[j], nums[k]]。

注意，解集不能包含重复的三元组。

解决方案 1

排序 + 双指针方法

Approach 1 / 方法 1

This solution uses sorting and the two-pointer technique. The idea is to fix one element and use two pointers to find the other two elements that sum up to zero.

该解决方案使用排序和双指针技术。其思想是固定一个元素，并使用两个指针找到其他两个元素，使它们的和为零。

Implementation / 实现

python

# Solution 1 implementation in Python
def threeSum(nums):
    nums.sort()
    res = []
    n = len(nums)

    for i in range(n):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # Skip duplicate elements
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                res.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1  # Skip duplicate elements
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1  # Skip duplicate elements
                left += 1
                right -= 1

    return res

Explanation / 解释

1. Step 1 / 第一步:

• Sort the array nums.
  将数组 nums 排序。

2. Step 2 / 第二步:

• Iterate through the array, fixing one element at a time.
  遍历数组，每次固定一个元素。

3. Step 3 / 第三步:

• Use two pointers (left and right) to find two other elements that sum up to zero with the fixed element.
  使用两个指针（left 和 right）找到另外两个元素，使它们与固定元素的和为零。

4. Step 4 / 第四步:

• If the sum is less than zero, move the left pointer to the right.
  如果和小于零，将 left 指针右移。

5. Step 5 / 第五步:

• If the sum is greater than zero, move the right pointer to the left.
  如果和大于零，将 right 指针左移。

6. Step 6 / 第六步:

• If the sum is zero, add the triplet to the result and skip duplicate elements.
  如果和为零，将三元组添加到结果中，并跳过重复元素。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n^2), where n is the number of elements in the array.
  时间复杂度: O(n^2)，其中n是数组中的元素数量。

• Space Complexity: O(1), excluding the space required for the output.
  空间复杂度: O(1)，不包括输出所需的空间。

Key Concept / 关键概念

• Sorting the array and using the two-pointer technique to find triplets efficiently.
  排序数组并使用双指针技术高效地找到三元组。

解决方案 2

哈希表方法 (仅用于理解，复杂度较高)

Approach 2 / 方法 2

This solution uses a hash table to store the complements of pairs of numbers and then checks for the third element.

该解决方案使用哈希表存储成对数的补数，然后检查第三个元素。

Implementation / 实现

python

# Solution 2 implementation in Python
def threeSum(nums):
    res = set()
    n = len(nums)
    for i in range(n):
        hashmap = {}
        for j in range(i + 1, n):
            complement = -nums[i] - nums[j]
            if complement in hashmap:
                res.add(tuple(sorted((nums[i], nums[j], complement))))
            hashmap[nums[j]] = j
    return list(res)

Explanation / 解释

1. Step 1 / 第一步:

• Initialize an empty set res to store unique triplets.
  初始化一个空集合 res 用于存储唯一的三元组。

2. Step 2 / 第二步:

• Iterate through the array, fixing one element at a time.
  遍历数组，每次固定一个元素。

3. Step 3 / 第三步:

• Use a hash table to store complements of pairs of numbers and check for the third element.
  使用哈希表存储成对数的补数，并检查第三个元素。

4. Step 4 / 第四步:

• If the complement is found in the hash table, add the sorted triplet to the result set.
  如果在哈希表中找到补数，将排序后的三元组添加到结果集中。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n^2), where n is the number of elements in the array.
  时间复杂度: O(n^2)，其中n是数组中的元素数量。

• Space Complexity: O(n), due to the hash table.
  空间复杂度: O(n)，由于哈希表。

Key Concept / 关键概念

• Using a hash table to find the third element for each pair of numbers.
  使用哈希表为每对数找到第三个元素。

Comparison / 比较

Comparison Between All Approaches

1. Algorithm:

   • Approach 1 (Sorting + Two-pointer Method):

     • Sorts the array and uses two pointers to find triplets.

   • Approach 2 (Hash Table Method):

     • Uses a hash table to store complements and find triplets.

2. Efficiency:

   • Time Complexity:

     • Both approaches have a time complexity of O(n^2), where n is the number of elements in the array.

   • Space Complexity:

     • The two-pointer method has a space complexity of O(1), excluding the output.
     • The hash table method has a space complexity of O(n) due to the hash table.

3. Readability and Maintainability:

   • Approach 1 (Sorting + Two-pointer Method):

     • Simple and efficient, making it easier to understand and maintain.

   • Approach 2 (Hash Table Method):

     • Slightly more complex due to the use of a hash table.

4. Best Practice:

   • Recommended Solution: Approach 1 (Sorting + Two-pointer Method):
     • Reason: Approach 1 is preferred due to its simplicity, efficiency, and minimal space usage.

Summary / 总结

• Use Approach 1 for a simple, efficient, and space-saving solution.
• Approach 1’s sorting and two-pointer method is straightforward and effective.

Tips / 提示

• Always sort the array first to simplify the two-pointer approach.
• Handle edge cases such as arrays with fewer than three elements or no valid triplets.

Solution Template for similar questions / 提示

• Use sorting and two-pointer methods to find triplets or pairs in array problems.
• Implement hash table methods for more complex scenarios if needed.

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of sorting, two-pointer techniques, and hash table usage in array problems.

5 more similar questions / 推荐5问题

1. LeetCode 1. Two Sum
2. LeetCode 18. 4Sum
3. LeetCode 16. 3Sum Closest
4. LeetCode 259. 3Sum Smaller
5. LeetCode 167. Two Sum II – Input array is sorted

Recommended Resources:

3Sum – Leetcode 15 – Python by NeetCode