LeetCode_15_3Sum

2019 年 04 月 09 日

955 次浏览

2929字数

1. 题目描述

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;
}

LeetCode_15_3Sum