15. 三数之和

题目描述

输入整数数组 nums。从中选出三个下标两两不同的元素，若它们的和为 0，就得到一个三元组。

返回所有这样的三元组。答案中不能有重复的三元组：元素相同的两个三元组只算一个。三元组之间的顺序、三元组内部的顺序都不限。

没有符合条件的三元组时，返回空数组。

示例 1

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

解释：(-1) + 0 + 1 = 0，(-1) + (-1) + 2 = 0。用不同下标组成的 [-1,0,1] 有两种，但只算一次。

示例 2

输入：nums = [0,1,1]
输出：[]

解释：仅有的一种选法和为 2，不是 0。

示例 3

输入：nums = [0,0,0]
输出：[[0,0,0]]

解释：仅有的一种选法和为 0。

数据范围

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

解题思路：排序 + 双指针

排序后固定 i，令 l=i+1、r=n-1。根据三数和与 0 的关系移动指针，并跳过相邻重复值，避免重复三元组。

为什么正确

固定 i 时，l 左侧已检查完，r 右侧已检查完；当前区间仍包含所有可能解。

复杂度分析

时间 O(n²)，额外空间 O(n)（Python 排序临时空间，不计输出）；若输出 m 个三元组，含输出空间 O(n+m)。

易错点

排序后仍要跳过固定位置和左右指针的重复值。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def threeSum(self, nums):
        nums.sort(); ans=[]
        for i in range(len(nums)-2):
            if i and nums[i] == nums[i-1]: continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i]+nums[l]+nums[r]
                if s == 0:
                    ans.append([nums[i],nums[l],nums[r]])
                    l += 1; r -= 1
                    while l < r and nums[l] == nums[l-1]: l += 1
                    while l < r and nums[r] == nums[r+1]: r -= 1
                elif s < 0: l += 1
                else: r -= 1
        return ans

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (s == 0) {
                    ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    l++; r--;
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                } else if (s < 0) l++;
                else r--;
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end()); vector<vector<int>> ans;
        for (int i = 0; i < (int)nums.size() - 2; i++) {
            if (i && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (s == 0) {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    l++; r--;
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                } else if (s < 0) l++;
                else r--;
            }
        }
        return ans;
    }
};

func threeSum(nums []int) [][]int {
	sort.Ints(nums); ans := [][]int{}
	for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		l, r := i+1, len(nums)-1
		for l < r {
			s := nums[i] + nums[l] + nums[r]
			if s == 0 {
				ans = append(ans, []int{nums[i], nums[l], nums[r]})
				l++; r--
				for l < r && nums[l] == nums[l-1] {
					l++
				}
				for l < r && nums[r] == nums[r+1] {
					r--
				}
			} else if s < 0 {
				l++
			} else {
				r--
			}
		}
	}
	return ans
}

var threeSum = function(nums) {
    nums.sort((a, b) => a - b); const ans = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i && nums[i] === nums[i - 1]) continue;
        let l = i + 1, r = nums.length - 1;
        while (l < r) {
            const s = nums[i] + nums[l] + nums[r];
            if (s === 0) {
                ans.push([nums[i], nums[l], nums[r]]);
                l++; r--;
                while (l < r && nums[l] === nums[l - 1]) l++;
                while (l < r && nums[r] === nums[r + 1]) r--;
            } else if (s < 0) l++;
            else r--;
        }
    }
    return ans;
};

function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b); const ans: number[][] = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i && nums[i] === nums[i - 1]) continue;
        let l = i + 1, r = nums.length - 1;
        while (l < r) {
            const s = nums[i] + nums[l] + nums[r];
            if (s === 0) {
                ans.push([nums[i], nums[l], nums[r]]);
                l++; r--;
                while (l < r && nums[l] === nums[l - 1]) l++;
                while (l < r && nums[r] === nums[r + 1]) r--;
            } else if (s < 0) l++;
            else r--;
        }
    }
    return ans;
};

载入编辑器，自己跑一遍 →

其他解法

两者都是先固定一个数，再用 O(n) 解决剩下的两数之和。双指针利用有序性，不需要额外空间；哈希法用空间换取思路上的直接。

解法 2：排序 + 固定一数后哈希两数之和时间 O(n²)，空间 O(n)

先排序。枚举第一个数 nums[i]，跳过与前一个相同的值。对 i 右侧的部分做「两数之和」：向右遍历 nums[j]，若 -nums[i]-nums[j] 已在哈希集合中就得到一组解，并跳过后续与 nums[j] 相同的数以去重；然后把 nums[j] 加入集合。

直接复用第 1 题「两数之和」的哈希思路，容易想到。但需要 O(n) 额外空间，哈希操作常数也更大，去重逻辑比双指针更容易写错。

class Solution:
    def threeSum(self, nums):
        nums.sort()
        ans = []
        for i in range(len(nums) - 2):
            if i and nums[i] == nums[i - 1]:
                continue
            seen = set()
            j = i + 1
            while j < len(nums):
                need = -nums[i] - nums[j]
                if need in seen:
                    ans.append([nums[i], need, nums[j]])
                    while j + 1 < len(nums) and nums[j + 1] == nums[j]:
                        j += 1
                seen.add(nums[j])
                j += 1
        return ans

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i + 2 < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            Set<Integer> seen = new HashSet<>();
            for (int j = i + 1; j < n; j++) {
                int need = -nums[i] - nums[j];
                if (seen.contains(need)) {
                    ans.add(Arrays.asList(nums[i], need, nums[j]));
                    while (j + 1 < n && nums[j + 1] == nums[j]) j++;
                }
                seen.add(nums[j]);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i + 2 < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            unordered_set<int> seen;
            for (int j = i + 1; j < n; j++) {
                int need = -nums[i] - nums[j];
                if (seen.count(need)) {
                    ans.push_back({nums[i], need, nums[j]});
                    while (j + 1 < n && nums[j + 1] == nums[j]) j++;
                }
                seen.insert(nums[j]);
            }
        }
        return ans;
    }
};

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	n := len(nums)
	ans := [][]int{}
	for i := 0; i+2 < n; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		seen := map[int]bool{}
		for j := i + 1; j < n; j++ {
			need := -nums[i] - nums[j]
			if seen[need] {
				ans = append(ans, []int{nums[i], need, nums[j]})
				for j+1 < n && nums[j+1] == nums[j] {
					j++
				}
			}
			seen[nums[j]] = true
		}
	}
	return ans
}

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const ans = [];
    for (let i = 0; i + 2 < n; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        const seen = new Set();
        for (let j = i + 1; j < n; j++) {
            const need = -nums[i] - nums[j];
            if (seen.has(need)) {
                ans.push([nums[i], need, nums[j]]);
                while (j + 1 < n && nums[j + 1] === nums[j]) j++;
            }
            seen.add(nums[j]);
        }
    }
    return ans;
};

function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const ans: number[][] = [];
    for (let i = 0; i + 2 < n; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        const seen = new Set<number>();
        for (let j = i + 1; j < n; j++) {
            const need = -nums[i] - nums[j];
            if (seen.has(need)) {
                ans.push([nums[i], need, nums[j]]);
                while (j + 1 < n && nums[j + 1] === nums[j]) j++;
            }
            seen.add(nums[j]);
        }
    }
    return ans;
};

双指针专题的其他题目

查看双指针全部题目 →