中文題目

給定一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

英文題目

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

解法一：

直接暴力求解，三變量，逐個循環(huán)，算法時間復(fù)雜度大致為，超時應(yīng)該是沒有任何問題，所以我并未嘗試，后來看網(wǎng)上相關(guān)題解，直接暴力的的確會超時

解法二：

既然暴力會直接超時，那么如何優(yōu)化呢？

—— 排序后再求解如何，排序作為重要且非常常用的算法，確實可以將許多問題變得簡單化

選用何種排序？

—— 為了降低時間復(fù)雜度，為之后的操作留下空間，所以，選擇快排或者歸并

原始思路：

我剛開始想的是：

• 將兩個指針指向數(shù)組兩邊，直至左邊大于右邊（此用while構(gòu)成一組循環(huán)）

• 再一指針置于左右的中間（此用for 構(gòu)成一重循環(huán)），直至等于右邊-1

但是在提交過程中遇到了困難，后經(jīng) 博客提點，發(fā)現(xiàn)自己的寫法不甚理想，遂改之

最終通過代碼如下：

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
void Merge(int a[], int l, int r, int rightEnd, int temp[]) {
    int leftEnd = r-1 ;
    int left = l, tmp = l;

    while (l <= leftEnd && r <= rightEnd){ // 當(dāng)左右子序列均不空
        if (a[l] > a[r])
            temp[tmp++] = a[r++];
        else
            temp[tmp++] = a[l++];
    }
    while (l <= leftEnd)
        temp[tmp++] = a[l++];
    while (r <= rightEnd)
        temp[tmp++] = a[r++];
    for (int i = left; i < rightEnd + 1; i++)
        a[i] = temp[i];
}


void MergeSort(int a[], int l, int rightEnd, int temp[]) {
    int center;
    if (l < rightEnd) {
        center = (l + rightEnd) / 2;
        MergeSort(a, l, center, temp);
        MergeSort(a, center + 1, rightEnd, temp);
        Merge(a, l, center+1, rightEnd, temp);
    }
}


void Merge_sort(int a[], int n) {
    int* tmpA;
    tmpA = malloc(n * sizeof(int));
    if (tmpA != NULL){
        MergeSort(a, 0, n-1, tmpA);
        free(tmpA);
    } else {
        printf("ERROR");
    }
}


int** threeSum(int* nums, int numsSize, int* returnSize) {
    if (numsSize < 3)
        return NULL;
    int i = 0, j, k, temp, count = 0;
    int** result=(int**)malloc(sizeof(int*)*(numsSize*(numsSize-1)*(numsSize-2))/6);
    Merge_sort(nums, numsSize);
    for (i = 0; i < numsSize; i++){
        if (nums[i] > 0)
            break;
        if (i > 0 && nums[i] == nums[i-1])  // 跳過重復(fù)負(fù)數(shù)
            continue;
        j = i+1;
        k = numsSize-1;
        while (j < k){
            temp = nums[i]+nums[j]+nums[k];
            if (temp == 0){
                result[count] = (int*)malloc(sizeof(int)*3);
                result[count][0] = nums[i];
                result[count][1] = nums[j];
                result[count][2] = nums[k];
                count++;
                j++;    k--;
                while (j <k && nums[j] == nums[j-1])    // 跳過重復(fù)數(shù)字
                    j++;
                while (j < k && nums[k] == nums[k+1])   // 跳過重復(fù)數(shù)字
                    k--;
            } else if (temp > 0)    // 右邊數(shù)字過大 
                k--;
            else    // 左邊數(shù)字過小
                j++;
        }
    }
    
    *returnSize = count;
    return result;
}

代碼解釋：

首先前三個函數(shù)實現(xiàn)歸并排序，void Merge_sort(int a[], int n)函數(shù)簡化函數(shù)接口，相關(guān)代碼實現(xiàn)借鑒 浙江大學(xué)慕課——數(shù)據(jù)結(jié)構(gòu)

主體函數(shù)采用二重循環(huán)，時間復(fù)雜度接近

1. 初始化數(shù)據(jù)
2. 將數(shù)組nums從小到大排序
3. 第一重循環(huán)為取出所有負(fù)數(shù)nums[i]
4. 第二重循環(huán)為從i+1開始numsSize-1結(jié)束，查找是否存在三數(shù)之和為0

代碼說明：

• 注意用指針的指針表示動態(tài)數(shù)組時的malloc()過程

LeetCode15.png