LeetCode 18. 4Sum ( C ) – Medium (雙指標法、搜尋法)
Posted On 2021 年 6 月 18 日
本題為 3Sum 、 3Sum Closest 的延伸題目，可以先看前面的題目再來看這題，會比較有連貫性。
本題題目為，給定一串數字，輸出任意4個數字相加，等於目標值的所有組合。
原文題目如下
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
解題策略分為兩總，( 1 ) 雙指標法，( 2 )搜尋法。
( 1 ) 雙指標法為，先排序整個數字陣列，再透過兩層迴圈遍歷數字，每次透過雙指標找出符合條件的值。
( 2 ) 搜尋法為，先排序整個數字陣列，再透過三層迴圈遍歷數字，每次透過二元搜尋找到符合的值。
下面是我的程式碼
( 1 ) 雙指標法
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int cmp(const void* a, const void* b){
return *(int*)a - *(int*)b;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
*returnSize = 0; // number of return pairs
int left,right;
int step = 4; // each memory alloc
*returnColumnSizes = (int*)malloc(sizeof(int*)*step);
int** re = (int**)malloc(sizeof(int*)*step);
qsort(nums, numsSize, sizeof(int), cmp);
for(int i = 0; i<numsSize-3 ; i++){
if(i!=0){ //Jump Same num
while(i<numsSize-3){
if(nums[i]==nums[i-1])
i++;
else
break;
}
}
if(i<numsSize-3){
for(int j = i+1; j<numsSize-2 ; j++ ){
if(j!=i+1){ //Jump Same num
while(j<numsSize-2){
if(nums[j]==nums[j-1])
j++;
else
break;
}
}
if(j<numsSize-2){
left = j+1;
right = numsSize-1;
while(right>left){
if((nums[i]+nums[j]+nums[left]+nums[right])==target){
if((*returnSize) != 0 && (*returnSize)%step == 0){
*returnColumnSizes = (int*)realloc(*returnColumnSizes, sizeof(int*) * ((*returnSize)+step));
re = (int**)realloc(re, sizeof(int*) * ((*returnSize)+step));
}
(*returnColumnSizes)[*returnSize] = 4;
re[*returnSize] = (int*)malloc(sizeof(int)*4);
re[*returnSize][0] = nums[i];
re[*returnSize][1] = nums[j];
re[*returnSize][2] = nums[left];
re[*returnSize][3] = nums[right];
(*returnSize)++;
left++;
while((left<numsSize) && (nums[left] == nums[left-1])){
left++;
}
right--;
while((right>=0) && (nums[right] == nums[right+1])){
right--;
}
}
else if((nums[i]+nums[j]+nums[left]+nums[right])<target){
left++;
while((left<numsSize) && (nums[left] == nums[left-1])){
left++;
}
}
else{
right--;
while((right>=0) && (nums[right] == nums[right+1])){
right--;
}
}
}
}
}
}
}
return re;
}
( 2 ) 搜尋法
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
void mergeSort(int* num, int numsSize);
void sortsub(int* num, int low, int high);
void merge(int* num, int low, int middleL, int middleR, int high);
bool binarySearch(int* nums, int left, int right, int target);
int cmp(const void* a, const void* b){
return *(int*)a - *(int*)b;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
*returnSize = 0; // number of return pairs
int step = 4; // each memory alloc
*returnColumnSizes = (int*)malloc(sizeof(int*)*step);
int** re = (int**)malloc(sizeof(int*)*step);
qsort(nums, numsSize, sizeof(int), cmp);
for(int i = 0; i<numsSize-3 ; i++){
if(i!=0){ //Jump Same num
while(i<numsSize-3){
if(nums[i]==nums[i-1])
i++;
else
break;
}
}
if(i<numsSize-3){
for(int j = i+1; j<numsSize-2 ; j++ ){
if(j!=i+1){ //Jump Same num
while(j<numsSize-2){
if(nums[j]==nums[j-1])
j++;
else
break;
}
}
if(j<numsSize-2){
for(int k = j+1; k<numsSize-1 ; k++ ){
if(k!=j+1){
while(k<numsSize-1){
if(nums[k]==nums[k-1])
k++;
else
break;
}
}
if(k<numsSize-1){
if(binarySearch(nums,k+1,numsSize-1,(target-nums[i]-nums[j]-nums[k]))){
if((*returnSize) != 0 && (*returnSize)%step == 0){
*returnColumnSizes = (int*)realloc(*returnColumnSizes, sizeof(int*) * ((*returnSize)+step));
=re = (int**)realloc(re, sizeof(int*) * ((*returnSize)+step));
}
(*returnColumnSizes)[*returnSize] = 4;
re[*returnSize] = (int*)malloc(sizeof(int)*4);
re[*returnSize][0] = nums[i];
re[*returnSize][1] = nums[j];
re[*returnSize][2] = nums[k];
re[*returnSize][3] = target-nums[i]-nums[j]-nums[k];
(*returnSize)++;
}
}
}
}
}
}
}
return re;
}
bool binarySearch(int* nums, int left, int right, int target) {
int middle;
if (target < nums[left] || target > nums[right])
return false;
while (left <= right) {
middle = (right + left) / 2;
if (nums[middle] == target) {
return true;
}
else if (target > nums[middle]) {
left = middle + 1;
}
else {
right = middle - 1;
}
}
return false;
}
下面是時間與空間之消耗
( 1 ) 雙指標法
Runtime: 48 ms, faster than 24.66% of C online submissions for 4Sum.
Memory Usage: 6.6 MB, less than 83.56% of C online submissions for 4Sum.
( 2 ) 搜尋法
Runtime: 56 ms, faster than 23.29% of C online submissions for 4Sum.
Memory Usage: 6.5 MB, less than 94.52% of C online submissions for 4Sum.
下一題連結 : LeetCode19. Remove Nth Node From End of List ( C ) – Medium
About The Author
