三数之和

题解思路

本题的目标是找到所有 和为 0 的 不重复三元组，并输出它们。

最直观的方法是 三重循环暴力枚举，但这样时间复杂度为 O(n³)，当 n = 3000 时会超时。

优化思路（双指针 + 排序）

1. 先对数组进行排序：这样可以更方便地去重，并利用双指针减少时间复杂度。
2. 固定一个数 nums[i]，然后在 i 右侧寻找两数之和等于 -nums[i]：
   • 双指针法：在 nums[i] 右侧，设定左指针 left = i+1，右指针 right = n-1，寻找满足 nums[i] + nums[left] + nums[right] = 0 的组合。
   • 若 nums[i] 和 nums[i-1] 相同，则跳过（避免重复）。
   • 调整指针：
     • 如果 nums[i] + nums[left] + nums[right] < 0，则 left++ 使总和变大。
     • 如果 nums[i] + nums[left] + nums[right] > 0，则 right-- 使总和变小。
     • 如果刚好等于 0，记录答案并跳过重复值。

复杂度分析

• 排序：O(n log n)
• 遍历每个元素并用双指针搜索：O(n²)
• 总时间复杂度：O(n²)（比 O(n³) 快很多，适用于本题）
• 空间复杂度：O(1)（仅使用了常数额外空间）

代码实现

Python 代码

class Solution:
    def threeSum(self, nums):
        """
        三数之和，双指针法
        :param nums: List[int] 代表输入数组
        :return: List[List[int]] 符合条件的三元组列表
        """
        nums.sort()  # 先排序
        n = len(nums)
        res = []

        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:  # 跳过重复元素
                continue

            left, right = i + 1, n - 1  # 左右指针
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    res.append([nums[i], nums[left], nums[right]])
                    # 跳过重复元素
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
        return res

# 读取输入
if __name__ == "__main__":
    n = int(input())  # 读取 n
    nums = list(map(int, input().split()))  # 读取数组
    solution = Solution()
    results = solution.threeSum(nums)
    for triplet in results:
        print(" ".join(map(str, triplet)))

Java 代码

import java.util.*;

public class Main {
    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums); // 先排序
            List<List<Integer>> res = new ArrayList<>();
            int n = nums.length;

            for (int i = 0; i < n - 2; i++) {
                if (i > 0 && nums[i] == nums[i - 1]) { // 跳过重复元素
                    continue;
                }
                int left = i + 1, right = n - 1;

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

                    if (total < 0) {
                        left++;
                    } else if (total > 0) {
                        right--;
                    } else {
                        res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        // 跳过重复值
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    }
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取 n
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        scanner.close();

        Main main = new Main();
        Solution solution = main.new Solution();
        List<List<Integer>> results = solution.threeSum(nums);
        for (List<Integer> triplet : results) {
            System.out.println(triplet.get(0) + " " + triplet.get(1) + " " + triplet.get(2));
        }
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 先排序
        vector<vector<int>> res;
        int n = nums.size();

        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复元素

            int left = i + 1, right = n - 1;
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];

                if (total < 0) {
                    left++;
                } else if (total > 0) {
                    right--;
                } else {
                    res.push_back({nums[i], nums[left], nums[right]});
                    // 跳过重复值
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
};

int main() {
    int n;
    cin >> n; // 读取 n
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    Solution solution;
    vector<vector<int>> results = solution.threeSum(nums);
    for (const auto& triplet : results) {
        cout << triplet[0] << " " << triplet[1] << " " << triplet[2] << endl;
    }

    return 0;
}

Leetcode 6.三数之和-原题链接

题目内容

给你一个整数数组$nums$ ，判断是否存在三元组 $[nums[i], nums[j], nums[k]]$ 满足 $i != j$、$i != k$ 且 $j != k$ ，同时还满足 $nums[i] + nums[j] + nums[k] == 0$ 。请你输出所有和为 $0$ 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

输入描述

输入共两行。

• 第一行为一个整数$n$，代表数组$nums$的长度。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-1}$，数字之间以空格分隔。

输出描述

输出所有满足条件的三元组。 每行代表一个三元组。三元组的数字之间以空格分隔。

样例1

输入

6 
-1 0 1 2 -1 -4

输出

-1 -1 2
-1 0 1

说明

$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$ 。

不同的三元组是 $[-1,0,1]$ 和 $[-1,-1,2]$。

注意，输出的顺序和三元组的顺序并不重要。

样例2

输入

3
0 1 1

输出

说明

唯一可能的三元组和不为 $0$。

样例3

输入

3
0 0 0

输出

0 0 0

说明

唯一可能的三元组和为 $0$。

提示

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