LeetCode - 15 三数之和

题目来源

15. 三数之和 - 力扣（LeetCode）

题目描述

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

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

示例 1

输入：nums = [-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

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示

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

题目解析

本题我们可以将 nums 进行升序

那么只要保证：i < j < k，即可实现 nums[i] <= nums[j] <= nums[k]

选取三元组时，我们可以固定 i 索引位置，然后初始 j = i + 1，k = nums.length - 1，如下图所示：

然后计算此时三元组之和：sum = nums[i] + nums[j] + nums[k]

• 若 sum > 0，则说明三元组之和偏大了，此时我们应该 k--，这样的话，三元组之和就会减小
• 若 sum < 0，则说明三元组之和偏小了，此时我们应该 j++，这样的话，三元组之和就会增大
• 若 sum == 0，则说明此时三元组是符合要求的，我们记录此时的三元组，然后 k-- ，j++

对于 nums = [-4, -1, -1, 0, 1, 2]，按照上面逻辑演示，过程如下：

本题需要我们求解不重复的三元组，但是我们通过上图发现，存在重复的三元组 [-1, 0, 1]，而造成重复的原因是 nums[1] == nums[2]。

如果 i = 1，那么可以产生的三元组（索引）有：

需要满足 i < j < k

• [i=1, j=2, k=5]
• [i=1, j=2, k=4]
• [i=1, j=2, k=3]
• [i=1, j=3, k=5]
• [i=1, j=3, k=4]
• [i=1, j=4, k=5]

如果 i = 2，那么可以产生的三元组（索引）有：

• [i=2, j=3, k=5]
• [i=2, j=3, k=4]
• [i=2, j=4, k=5]

那么，nums[1] == nums[2] 的话，那么 i = 1可以产生的三元组是可以完全覆盖 i = 2 产生的三元组的（三元组各元素值相同）。

因此当 nums[i] == nums[i-1] 时，我们就可以跳过 nums[i] 产生三元组的过程，因为必然和 nums[i-1] 产生的三元组发生重复。

除了上面情况会产生重复三元组外，还有一种情况，比如 nums = [-2, 0, 0, 2, 2]，如下图所示，会产生重复三元组 [-2, 0, 2]

造成重复的原因是：

• 如果 j++ 后，nums[j] == nums[j - 1]，则会产生重复三元组
• 如果 k-- 后，nums[k] == nums[k+1]，则会产生重复三元组

为了避免产生重复三元组，我们可以在 j++ 或 k-- 过程中，跳过相同元素。

C源码实现

C语言这题比较难以理解是函数参数 int* returnSize 和 int** returnColumnSizes。

我们返回的结果是一个 int** 类型的，主要记录不重复的三元组，比如 [[-1,-1,2], [-1,0,1]]，可以发现返回值本质是一个二维数组。

而 returnSize 记录的其实就是返回值二维数组的行数，returnColumnSizes记录的是返回值二维数组每行的列数。

比如对于返回值 [[-1,-1,2], [-1,0,1]] 来说，returnSize = 2，returnColumnSizes = [3, 3]

而本题 returnSize 和 returnColumnSizes 参数类型都是指针，即调用 threeSum 函数时，传递的时 returnSize 和 returnColumnSizes 的指针（地址）。大家可以对照下面代码注释中 main 函数调用 threeSum函数 时的传参来理解。

#include <stdio.h>
#include <stdlib.h>/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume* caller calls free().*/
int cmp(const void *a, const void *b) { return *(int *) a - *(int *) b; }int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {// 记录结果int **res = (int **) malloc(sizeof(int *) * 20000);int res_size = 0;// nums升序qsort(nums, numsSize, sizeof(nums[0]), cmp);for (int i = 0; i < numsSize - 2; i++) { // i作为三元组中最小元素的索引位置if (nums[i] > 0) {// 由于nums已经升序,因此nums[i]>0时, 而 nums[r] >= nums[l] >= nums[i], 因此之后三数之和必然大于0break;}if (i > 0 && nums[i] == nums[i - 1]) {// 去重continue;}// 双指针int l = i + 1;int r = numsSize - 1;while (l < r) {// 三数之和int sum = nums[i] + nums[l] + nums[r];if (sum > 0) {// r左移, 三数之和减少r--;} else if (sum < 0) {// l右移, 三数之和增加l++;} else {// 三数之和为0时, 此时三元组是符合题目要求的res[res_size++] = (int *) malloc(sizeof(int) * 3);res[res_size - 1][0] = nums[i];res[res_size - 1][1] = nums[l];res[res_size - 1][2] = nums[r];// 去重do {l++;} while (l < r && nums[l] == nums[l - 1]);// 去重do {r--;} while (r > l && nums[r] == nums[r + 1]);}}}*returnSize = res_size; // returnSize 记录 res 行数, 本质是一个int值, 只是参数传递时, 取地址变为了 int* 类型*returnColumnSizes = (int *) malloc(sizeof(int) * res_size); // returnColumnSizes 记录 res 每一行的列数, 本质是一个int一维数组, 只是参数传递时, 取地址变为了 int** 类型for (int i = 0; i < res_size; i++) {(*returnColumnSizes)[i] = 3;}return res;
}//int main() {
//    int nums[] = {-1, 0, 1, 2, -1, -4};
//    int numSize = 6;
//
//    int returnSize; // 记录结果行数
//    int *returnColumnSizes; // 记录结果的每一行列数
//
//    // int returnSize 取地址后变为 int* 类型
//    // int* returnColumnSizes 取地址后变为 int** 类型
//    int **res = threeSum(nums, numSize, &returnSize, &returnColumnSizes);
//
//    for (int i = 0; i < returnSize; i++) {
//        printf("[");
//        for (int j = 0; j < returnColumnSizes[i]; j++) {
//            printf("%d", res[i][j]);
//
//            if (j < returnColumnSizes[i] - 1) {
//                printf(",");
//            }
//        }
//        printf("]\n");
//    }
//
//
//    return 0;
//}

C++源码实现

class Solution {
public:vector<vector<int>> threeSum(vector<int> &nums) {vector<vector<int>> res;// nums升序sort(nums.begin(), nums.end());for (int i = 0; i < nums.size() - 2; i++) { // i作为三元组中最小元素的索引位置if (nums[i] > 0) {// 由于nums已经升序,因此nums[i]>0时, 而 nums[r] >= nums[l] >= nums[i], 因此之后三数之和必然大于0break;}if (i > 0 && nums[i] == nums[i - 1]) {// 去重continue;}// 双指针int l = i + 1;int r = nums.size() - 1;while (l < r) {// 三数之和int sum = nums[i] + nums[l] + nums[r];if (sum > 0) {// r左移, 三数之和减少r--;} else if (sum < 0) {// l右移, 三数之和增加l++;} else {// 三数之和为0时, 此时三元组是符合题目要求的res.emplace_back(vector<int>{nums[i], nums[l], nums[r]});// 去重do {l++;} while (l < r && nums[l] == nums[l - 1]);// 去重do {r--;} while (r > l && nums[r] == nums[r + 1]);}}}return res;}
};

Java源码实现

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> lists = new ArrayList<>();// nums升序Arrays.sort(nums);for (int i = 0; i < nums.length - 2; i++) {if (nums[i] > 0) {// 由于nums已经升序,因此nums[i]>0时, 而 nums[r] >= nums[l] >= nums[i], 因此之后三数之和必然大于0break;}if (i > 0 && nums[i] == nums[i - 1]) {// 去重continue;}// 双指针int l = i + 1;int r = nums.length - 1;while (l < r) {// 三数之和int sum = nums[i] + nums[l] + nums[r];if (sum > 0) {// r左移, 三数之和减少r--;} else if (sum < 0) {// l右移, 三数之和增加l++;} else {// 三数之和为0时, 此时三元组是符合题目要求的ArrayList<Integer> list = new ArrayList<>();Collections.addAll(list, nums[i], nums[l], nums[r]);lists.add(list);// 去重do {r--;} while (r > l && nums[r] == nums[r + 1]);// 去重do {l++;} while (l < r && nums[l] == nums[l - 1]);}}}return lists;}
}

Python源码实现

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""# nums升序nums.sort()res = []for i in range(len(nums) - 2):  # i作为三元组中最小元素的索引位置if nums[i] > 0:# 由于nums已经升序,因此nums[i]>0时, 而 nums[r] >= nums[l] >= nums[i], 因此之后三数之和必然大于0breakif i > 0 and nums[i] == nums[i - 1]:# 去重continue# 双指针l = i + 1r = len(nums) - 1while l < r:# 三数之和total = nums[i] + nums[l] + nums[r]if total > 0:# r左移, 三数之和减少r -= 1elif total < 0:# l右移, 三数之和增加l += 1else:# 三数之和为0时, 此时三元组是符合题目要求的res.append((nums[i], nums[l], nums[r]))l += 1r -= 1# 去重while l < r and nums[l] == nums[l - 1]:l += 1continue# 去重while r > l and nums[r] == nums[r + 1]:r -= 1continuereturn res

JavaScript源码实现

/*** @param {number[]} nums* @return {number[][]}*/
var threeSum = function (nums) {// nums升序nums.sort((a, b) => a - b);const res = [];for (let i = 0; i < nums.length - 2; i++) {// i作为三元组中最小元素的索引位置if (nums[i] > 0) {// 由于nums已经升序,因此nums[i]>0时, 而 nums[r] >= nums[l] >= nums[i], 因此之后三数之和必然大于0break;}if (i > 0 && nums[i] == nums[i - 1]) {// 去重continue;}// 双指针let l = i + 1;let r = nums.length - 1;while (l < r) {// 三数之和const sum = nums[i] + nums[l] + nums[r];if (sum > 0) {// r左移, 三数之和减少r--;} else if (sum < 0) {// l右移, 三数之和增加l++;} else {// 三数之和为0时, 此时三元组是符合题目要求的res.push([nums[i], nums[l], nums[r]]);// 去重do {l++;} while (l < r && nums[l] == nums[l - 1]);// 去重do {r--;} while (r > l && nums[r] == nums[r + 1]);}}}return res;
};