题目

英文

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

1
2
3
4
5
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

中文

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

1
2
3
4
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

  • 对数据进行排序（将三数之和转化为两数之和，减少时间复杂度）
  • 遍历,取当前节点以及当前节点右边非重复两个值（这里利用双指针），比对三个值的和是否等于0。
  • 因为比对的结果是0，且除当前节点外的两个节点都大于当前节点，所以如果当前节点大于0，则停止遍历

    原思路

    暴力循环寻找最优解，但是时间复杂度变成n^3,会超时。

    优化思路

  • 首先对数组进行排序（最好快排）
  • 循环数组，当前节点为i
  • 定义两个指针 j (j=i+1)、 k (k=numssize-1),依据条件（nums[j] + nums[j] + nums[k] == 0）遍历寻找最优解。
  • 如果最小节点i > 0，则无需继续循环。
    优化后代码时间复杂度由原来的n^3变为n^2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
void bubbleSort(int *nums, int lenNums) {
    int i, j;
    int tmp;
    int flag = 1;
    for (i = 0; i < lenNums; i++) {
        for (j = 0; j < lenNums - 1; ++j) {
            if (nums[j + 1] < nums[j]) {
                tmp = nums[j + 1];
                nums[j + 1] = nums[j];
                nums[j] = tmp;
                flag = 0;
            }
        }
        if (flag == 1) {
            break;
        }
    }
}
/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int **threeSum(int *nums, int numsSize, int *returnSize) {
    int i, j, k, m;
    int **ret = malloc(sizeof(int ) * (numsSize*(numsSize-1)*(numsSize-2))/6);
    *returnSize = 0;
    bubbleSort(nums, numsSize);
    for (i = 0; i < numsSize; i++) {
        if (i > 0 && nums[i - 1] == nums[i]) {
            continue;
        }
        if(nums[i] > 0)
        {
            break;
        }
        j = i + 1;
        k = numsSize - 1;
        while (k > j) {
            if (nums[j] + nums[k] + nums[i]== 0) {
                ret[*returnSize] = (int *) malloc(sizeof(int) * 3);
                ret[*returnSize][0] = nums[i];
                ret[*returnSize][1] = nums[j];
                ret[*returnSize][2] = nums[k];
                j++;
                k--;
                (*returnSize)++;
                while (j < k && nums[j] == nums[j - 1]) {
                    j++;
                }
                while (j < k && nums[k] == nums[k + 1]) {
                    k--;
                }
                continue;
            }
            if (nums[j] + nums[k] + nums[i] > 0) {
                k--;
                continue;
            }
            if (nums[j] + nums[k] + nums[i] < 0) {
                j++;
                continue;
            }
        }
    }
    return ret;
}