15. 三数之和

题目

给你一个整数数组 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

有两种解法，双指针更优，但是为了练习dfs还是先写了dfs

代码

完整代码

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

void dfs(int *arr, int index1, int index2, int index3, int arrsize, int **res, int* returnSize) {
    if (index3 >= arrsize) {
        return;
    } else {
        if (arr[index1] + arr[index2] + arr[index3] == 0) {
            int saved = 0;
            for (int i = 0; i < (*returnSize); i++) {
                if (res[i][0] == arr[index1] &&
                    res[i][1] == arr[index2] &&
                    res[i][2] == arr[index3]) {
                    saved = 1;
                    break;
                }
            }
            if (saved == 0) {
                res[(*returnSize)] = (int*)calloc(3, sizeof(int));
                res[(*returnSize)][0] = arr[index1];
                res[(*returnSize)][1] = arr[index2];
                res[(*returnSize)][2] = arr[index3];
                (*returnSize)++;
            }
        }
        dfs(arr, index1, index2, index3 + 1, arrsize, res, returnSize);
    }
    return;
}

int cmp(const void *a, const void *b) {
    return (*(int*)a) - (*(int*)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    qsort(nums, numsSize, sizeof(int), cmp); // 排序数组
    
    int** res = (int**)calloc(10000, sizeof(int*));
    for (int i = 0; i < numsSize - 2; i++) {
        for (int j = i + 1; j < numsSize - 1; j++) {
            dfs(nums, i, j, j + 1, numsSize, res, returnSize);
        }
    }
    
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < (*returnSize); i++) {
        (*returnColumnSizes)[i] = 3;
    }
    
    return res;
}

思路分析

本算法利用深度优先搜索（DFS）来查找所有满足 nums[i] + nums[j] + nums[k] == 0 的三元组。首先对数组进行排序，然后通过两层循环遍历数组中的每个元素组合，递归检查是否有符合条件的三元组。

拆解分析

1. 排序数组：首先对输入数组进行排序，便于后续查找。
2. 初始化结果存储结构：初始化结果存储结构 res 和 returnSize。
3. 两层循环遍历数组：通过两层循环遍历数组中的每个元素组合。
4. 递归查找三元组：在每个组合中，递归检查是否有满足条件的三元组。
5. 去重：在保存三元组之前，检查是否已经存在，避免重复。
6. 返回结果：将结果存储在 res 中，并返回结果及其大小。

复杂度分析

• 时间复杂度：O(n^3)，其中 n 是数组的长度。需要遍历所有的三元组组合。
• 空间复杂度：O(n)，用于存储结果的动态数组和递归调用栈。

一题多解

双指针法

双指针法思路分析

1. 排序数组：首先对输入数组进行排序。
2. 遍历数组：遍历数组中的每个元素，固定一个元素 nums[i]。
3. 双指针查找：在剩余部分用双指针查找两个元素，使得三个元素的和为零。
4. 去重处理：在移动指针时，跳过重复元素，避免结果中出现重复三元组。

双指针法复杂度分析

• 时间复杂度：O(n^2)，排序需要 O(n log n)，遍历和双指针查找需要 O(n^2)。
• 空间复杂度：O(1)，除了存储结果的空间外，不需要额外的空间。

双指针法代码

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(int*)a) - (*(int*)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    qsort(nums, numsSize, sizeof(int), cmp); // 排序数组

    int** res = (int**)malloc(numsSize * numsSize * sizeof(int*));
    for (int i = 0; i < numsSize; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
        int left = i + 1;
        int right = numsSize - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res[*returnSize] = (int*)malloc(3 * sizeof(int));
                res[*returnSize][0] = nums[i];
                res[*returnSize][1] = nums[left];
                res[*returnSize][2] = nums[right];
                (*returnSize)++;
                while (left < right && nums[left] == nums[left + 1]) left++; // 去重
                while (left < right && nums[right] == nums[right - 1]) right--; // 去重
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    *returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = 3;
    }

    return res;
}

结果

DFS结果

dfs会超时，因为是O(n^3)

双指针结果

正常通过