Leetcode c语言-3Sum Closest

小灰灰 2021-03-28 14:17 426阅读 0赞

Title:

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

For example, given array S = {-1 2 1 -4}, and target = 1.
    
        The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

这道题和上道题类似，这次是要找到三个数的和最接近target。但是要注意的是我们需要返回的是和，而不是数组的元素，因此我们要做的就是遍历所有三个数，然后算出和，并与上次的结果比较，得到更小的。

贴出代码：

/*冒泡排序，flag的作用是判断如果发现有一次排序中没有数据交换，说明已经排序完毕，直接跳出*/
    void bubblesort(int *nums, int numsSize) {
        int i,j;
        int temp;
        int flag=1;
        
        for (i=0;i<numsSize;i++) {
            for (j=0;j<numsSize-1;j++) {
                if (nums[j+1]<nums[j]) {
                    temp=nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                    flag=0;
                }
            }
            if (flag==1)
                break;
        }
    }
    
    int threeSumClosest(int* nums, int numsSize, int target) {  
        int begin,end,i,sum,Min=INT_MAX;  
        bubblesort(nums,numsSize);  
        for(i=0;i<numsSize-2;i++){  
            if(i>0 && nums[i]==nums[i-1])continue;  
            begin=i+1;end=numsSize-1;  
            while(begin<end){  
                sum=nums[i]+nums[begin]+nums[end];  
                if(abs(sum-target)<abs(Min))Min=sum-target;  
                if(sum==target)return target;  
                else if(sum>target)end--;  
                else begin++;  
            }  
        }  
        return Min+target;  
    }

注意，这道题给出的target其实和上道题的0一样，我们只需要判定三个数的和如果大于target，那么end--，也就是右边的数左移一位；如果小于target，那么begin++，左边的数右移一位。

然后对于遍历的每一组元素，进行相加并与上一次的进行判断大小，如果更小，那么保存该相加的和。