1. 题目描述

problem link

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],

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

2. 解题

想了半天还是没什么思路,最坏的方法无疑是暴力三重循环,而且三重循环时间复杂度高,还不好排除重复结果,无奈,只能去看评论区的大佬们的方法了。

有一个O(N^2)的思路,和大家分享一下,这个答案的精髓之一在于先把整个数组排序,一个排好序的数组就可以消去三层循环中的一层,从而只剩两层循环,下面是详细过程。

假设现在的数组已经排好序了,首先最外层循环用 i 遍历一遍数组元素,假设这层循环选择的元素是nums[ i ],那么我们就要在数组下标为i之后的剩余部分找另外两个元素加起来等于 -nums[ i ],由于这是有序数组,所以我们可以这么找:一个front记录剩余元素区的第一个元素,一个back记录剩余元素区的最后一个元素,可知front记录的元素是这个区域的最小值,back记录的元素是这个区域的最大值,然后判断front+back等不等于-nums[ i ],如果大于,则back -= 1,如果小于,则让front += 1。用这种方法就可以把寻找两个元素用一层循环完成。

还有要注意的地方是排除重复结果。在找到一组front+back = -nums[ i ]后,我们判断front下一个元素还等不等于front,然后一直找到下一个不等于front的元素,back类似,找到下一个不等于back的元素再继续判断。以及最外层的i变化的时候,我们也要直接跳到下一个不等于i的元素。这三次判断就可以解决排除重复结果的问题。

相隔多天后的更新:

今天做了一道类似的题,所以回来看了看这道3Sum,忽然发现有些地方感觉不太顺畅。

在有序数组的左边界和右边界分别设置front和back,通过左移back和右移front这种方法把在数组中寻找特定的数的时间复杂度缩短到O(N),这个方法我当时看到的时候感觉十分符合直觉,但当我今天又回过头来看了一遍这个方法,感觉虽然符合直觉但不能确定一定是对的,可能我经常会钻这种牛角尖哈哈,所以在这里更新一下用单独的证明证明这个方法的正确性。

首先我们有一个排好序的数组,假设其中的元素是1 2 3 4 5 6 7,然后现在假设3 和 5的和是我们寻找的上面算法中的-nums[ i ],也就是说我们希望最终front和back能分别指向3和5。根据算法的步骤,可知要么front先到达3要么back先到达5,现假设front先到达3,如上图所示。那么注意,target等于3 + 5,所以back在5右边的时候加起来的和恒大于target,所以back此时会一直左移直到5,而3在此过程中不会变。所以最终一定能找到3 + 5,证毕。

3. 代码

这个代码还有些问题,因为我不知道最后会找到几组答案,所以我的二级指针要一直用realloc来变化大小,正常情况下这肯定是没问题的,但是在LeetCode下一个超大数据量的测试用例里,报了Memory Limit Exceeded错误,无奈,想不到什么好的方法代替realloc。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int* arr, int left, int right) {
    int l = left, r = left + 1;
    int pivot = arr[left];

    while (r <= right) {
        if (arr[r] < pivot) {
            swap(&arr[r], &arr[l + 1]);
            l++;
        }
        r++;
    }

    swap(&arr[l], &arr[left]);
    return l;
}

void __quick_sort(int* arr, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(arr, left, right);
        __quick_sort(arr, left, pivotIndex);
        __quick_sort(arr, pivotIndex + 1, right);
    }
}

void quick_sort(int* arr, int size) {
    __quick_sort(arr, 0, size - 1);
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
    if (numsSize < 3) {
        return NULL;
    }
    if (nums == NULL) {
        return NULL;
    }

    quick_sort(nums, numsSize);

    int** res = NULL;
    *returnSize = 0;

    for (int i = 0; i < numsSize; i++) {
        int target = -nums[i];
        int front = i + 1;
        int back = numsSize - 1;

        while (front < back) {
            int sum = nums[front] + nums[back];

            if (sum < target) {
                front++;
            }
            else if (sum > target) {
                back--;
            }
            else {  // 找到了
                (*returnSize)++;

                res = (int **)realloc(res, sizeof(int*) * (*returnSize));
                res[*returnSize - 1] = (int *)malloc(sizeof(int) * 3);
                res[*returnSize - 1][0] = nums[i];
                res[*returnSize - 1][1] = nums[front];
                res[*returnSize - 1][2] = nums[back];

                // 跳过和nums[front]重复的元素
                while (front < back && nums[front] == res[*returnSize - 1][1]) {
                    front++;
                }

                // 跳过和nums[back]重复的元素
                while (front < back && nums[back] == res[*returnSize - 1][2]) {
                    back--;
                }
            }
        }

        // 跳过和nums[i]重复的元素
        while (i + 1 < numsSize && nums[i + 1] == nums[i]) {
            i++;
        }
    }

    return res;
}

int main() {
    int nums[] = { -1, 0, 1, 2, -1, -4 };
    int returnSize = -1;
    int** res = threeSum(nums, sizeof(nums) / sizeof(int), &returnSize);

    system("pause");
    return 0;
}
Last modification:September 8th, 2019 at 08:25 pm