题解 | 三数之和

1、解题思路

1. 排序法： 首先将数组排序，这样可以方便地跳过重复元素。固定一个元素 nums[i]，然后在剩下的数组中使用双指针法寻找 nums[left] 和 nums[right]，使得 nums[i] + nums[left] + nums[right] = 0。为了避免重复，当发现相同的元素时，跳过它们。时间复杂度：O(n^2)，空间复杂度：O(1)（不考虑结果存储空间）。
2. 哈希表法： 使用哈希表来存储所有可能的二元组，然后遍历数组寻找第三个元素。这种方法需要额外的空间来存储中间结果，且时间复杂度较高。时间复杂度：O(n^2)，空间复杂度：O(n)。不符合题目对空间复杂度的要求。
3. 暴力法： 三重循环遍历所有可能的三元组，检查是否满足条件。时间复杂度：O(n^3)，空间复杂度：O(1)。效率太低，不适用于大规模数据。

2、代码实现

C++

#include <algorithm>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > threeSum(vector<int>& num) {
        // write code here
        vector<vector<int>> result;
        int n = num.size();
        if (n < 3) {
            return result;
        }
        sort(num.begin(), num.end());
        for (int i = 0; i < n - 2; ++i) {
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = num[i] + num[left] + num[right];
                if (sum == 0) {
                    result.push_back({num[i], num[left], num[right]});
                    while (left < right && num[left] == num[left + 1]) {
                        ++left;
                    }
                    while (left < right && num[right] == num[right - 1]) {
                        --right;
                    }
                    ++left;
                    --right;
                } else if (sum < 0) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
        return result;
    }
};

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def threeSum(self , num: List[int]) -> List[List[int]]:
        # write code here
        result = []
        n = len(num)
        if n < 3:
            return result
        num.sort()
        for i in range(n - 2):
            if i > 0 and num[i] == num[i - 1]:
                continue
            left, right = i + 1, n - 1
            while left < right:
                total = num[i] + num[left] + num[right]
                if total == 0:
                    result.append([num[i], num[left], num[right]])
                    while left < right and num[left] == num[left + 1]:
                        left += 1
                    while left < right and num[right] == num[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif total < 0:
                    left += 1
                else:
                    right -= 1
        return result

3、复杂度分析

1. 排序法： 排序后可以方便地跳过重复元素，避免重复的三元组。使用双指针法可以高效地找到满足条件的三元组。
2. 效率： 时间复杂度：O(n^2)，排序的时间复杂度为 O(nlogn)，双指针遍历的时间复杂度为 O(n^2)。空间复杂度：O(1)（不考虑结果存储空间）。
3. 边界条件： 数组长度小于3时，直接返回空列表。数组排序后，跳过重复元素以避免重复的三元组。
4. 适用性： 排序法是解决此问题的最优解，尤其适用于大规模数据。如果允许使用额外空间，哈希表法也可以考虑，但空间复杂度较高。