LeetCode 16. 3Sum Closest ( C )-Medium

Posted On 2021 年 6 月 9 日

這題是 LeetCode 15. 3Sum ( C )-Medium 的變形題。

題目為給定一串數字，尋找任意三個數字相加最接近目標值，並輸出這三個數字的合。

原文題目如下

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.


Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
 
Constraints:

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

下面分三總解法 1.暴力解、2.雙指標( Merge Sort )、3.雙指標( Quick Sort )

1 . 策略為開三個迴圈一個個比較

2 . 解題策略為使用雙指標，先透過 Merge Sort 將數列排序，使用 for 迴圈遍歷數列到倒數第三個數字，每次透過兩個指標逼近數字。

3 . 解題策略為使用雙指標，先透過 Quick Sort 將數列排序，使用 for 迴圈遍歷數列到倒數第三個數字，每次透過兩個指標逼近數字。

下面是我的程式碼

1 . 暴力解

int threeSumClosest(int* nums, int numsSize, int target){
    if(numsSize<3)
        return 0;
    else{
        int closest= -999999;
        for(int i = 0 ; i < numsSize-2 ; i++ ){
            for(int j = i+1 ; j < numsSize-1 ; j++ ){
                for(int k = j+1;k<numsSize;k++){
                    if(abs(target - (nums[i]+nums[j]+nums[k]))<abs(target-closest))
                        closest = (nums[i]+nums[j]+nums[k]);
                }
            }
        }
        return closest;
    }
}

2 . 雙指標( Merge Sort )

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

int threeSumClosest(int* nums, int numsSize, int target){
    int left = 0,right = 99999,closest = 99999,tempsum=0;
    mergeSort(nums,numsSize);
    
    for(int i = 0;i<numsSize-2;i++){
        left = i+1;
        right = numsSize-1;
        while(right>left){
            tempsum = nums[i]+nums[left]+nums[right];
            if(abs(target - tempsum)<abs(target - closest)){
                closest = tempsum;
            }
            if(tempsum<target){
                left++;
            }   
            else if(tempsum>target){
                right--;
            }
            else{
                break;
            }
        }
    }
    
    return closest;
}

void mergeSort(int* num, int numsSize) {
    sortsub(num, 0, numsSize - 1);
}

void sortsub(int* num, int low, int high) {
    if ((high - low) >= 1) {
        int middleL = (low + high) / 2;
        int middleR = middleL + 1;
        sortsub(num, low, middleL);
        sortsub(num, middleR, high);
        merge(num,low,middleL,middleR,high);
    }

}

void merge(int *num,int low,int middleL,int middleR, int high) {
    int combinedIndex = 0, leftIndex = low, rightIndex = middleR;
    int* tempArray = (int*)malloc(sizeof(int) * (high - low + 1));

    while (leftIndex <= middleL && rightIndex <= high) {
        if (num[leftIndex] < num[rightIndex]) {
            tempArray[combinedIndex++] = num[leftIndex++];
        }
        else
            tempArray[combinedIndex++] = num[rightIndex++];    
    }

    if (leftIndex > middleL) {
        while (rightIndex <= high) {
            tempArray[combinedIndex++] = num[rightIndex++];
        }
    }
    else {
        while (leftIndex <= middleL) {
            tempArray[combinedIndex++] = num[leftIndex++];
        }
    }

    for (int i = low; i <= high; i++) {
        num[i] = tempArray[i - low];
    }
}

3 . 雙指標( Quick Sort )

int cmp(const void *a, const void *b){
    return *(int *)a - *(int *)b;
}


int threeSumClosest(int* nums, int numsSize, int target){
    int left = 0,right = 99999,closest = 99999,tempsum=0;
    qsort(nums, numsSize, sizeof(int), cmp);    // quick sort
    for(int i = 0;i<numsSize-2;i++){
        left = i+1;
        right = numsSize-1;
        while(right>left){
            tempsum = nums[i]+nums[left]+nums[right];
            if(abs(target - tempsum)<abs(target - closest)){
                closest = tempsum;
            }
            if(tempsum<target){
                left++;
            }   
            else if(tempsum>target){
                right--;
            }
            else{
                break;
            }
        }
    }
    return closest;
}

下面是時間與空間之消耗

1 . 暴力解

Runtime: 316 ms, faster than 10.98% of C online submissions for 3Sum Closest.

Memory Usage: 5.8 MB

2 . 雙指標( Merge Sort )

Runtime: 20 ms, faster than 36.99% of C online submissions for 3Sum Closest.

Memory Usage: 7.9 MB

3 . 雙指標( Quick Sort )

Runtime: 8 ms, faster than 73.41% of C online submissions for 3Sum Closest.

Memory Usage: 5.9 MB, less than 65.90% of C online submissions for 3Sum Closest.

採用雙指標後大幅的提升執行效率，採用Quick Sort 又能稍微的提升速度。

下一題連結 : LeetCode 17. Letter Combinations of a Phone Number ( C ) – Medium (遞迴法)