中文題目
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums购对，判斷 nums 中是否存在三個(gè)元素 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]
]
解法一：
直接暴力求解窘拯，三變量红且，逐個(gè)循環(huán)，算法時(shí)間復(fù)雜度大致為涤姊，超時(shí)應(yīng)該是沒有任何問題直焙，所以我并未嘗試，后來看網(wǎng)上相關(guān)題解砂轻，直接暴力的的確會超時(shí)
解法二：
既然暴力會直接超時(shí)奔誓，那么如何優(yōu)化呢？
—— 排序后再求解如何搔涝，排序作為重要且非常常用的算法厨喂，確實(shí)可以將許多問題變得簡單化
選用何種排序？
—— 為了降低時(shí)間復(fù)雜度庄呈，為之后的操作留下空間蜕煌，所以，選擇快排或者歸并
原始思路：
我剛開始想的是：
將兩個(gè)指針指向數(shù)組兩邊诬留，直至左邊大于右邊（此用while構(gòu)成一組循環(huán)）
再一指針置于左右的中間（此用for 構(gòu)成一重循環(huán)）斜纪，直至等于
右邊-1
但是在提交過程中遇到了困難，后經(jīng) 博客提點(diǎn)文兑，發(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;
}
代碼解釋：
首先前三個(gè)函數(shù)實(shí)現(xiàn)歸并排序，void Merge_sort(int a[], int n)函數(shù)簡化函數(shù)接口绿贞，相關(guān)代碼實(shí)現(xiàn)借鑒 浙江大學(xué)慕課——數(shù)據(jù)結(jié)構(gòu)
主體函數(shù)采用二重循環(huán)因块，時(shí)間復(fù)雜度接近
- 初始化數(shù)據(jù)
- 將數(shù)組
nums從小到大排序 - 第一重循環(huán)為取出所有負(fù)數(shù)
nums[i] - 第二重循環(huán)為從
i+1開始numsSize-1結(jié)束，查找是否存在三數(shù)之和為0
代碼說明：
- 注意用指針的指針表示動態(tài)數(shù)組時(shí)的
malloc()過程
