最接近的三数之和

发布于 2020-07-15 16:28:14   阅读量 49  点赞 0  

原题地址:https://leetcode-cn.com/problems/3sum-closest/

题目

 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。


提示:

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



解法

 本题若使用暴力枚举法,时间复杂度将为 O(n^3),于是需要降低时间复杂度。先将数组进行排序,时间复杂度将为 o(n\log_2{n}),再考虑使用双指针法。

 遍历有序数组中每个元素,对于每个元素的下标i,令指针start=i+1即该元素之后第一个元素;指针end=nums.len-1即数组最后一个元素。若sum=nums[i]+nums[start]+nums[end]target之间的距离(绝对值)小于历史值,对待返回结果进行更新,同时对sum进行判断:

  • sum=target,则直接返回;

  • sum>target,则end--

  • sum<target,则start++

 本质上也是遍历三个数的组合之和,但通过将数组排序为单调与使用双指针,并对组合结果进行判断,使得组合的结果不会一直偏离target,而是在target附近改变,从而排除掉结果与target差值(即距离)一直增大的无效情况,将遍历的时间复杂度降为 O(n^2)

 于是算法总的时间复杂度为 O(n\log_2{n})+O(n^2)=O(n^2)



代码

int threeSumClosest(vector<int>& nums, int target) {
    int len = nums.size();

    quickSort(nums,0,len-1);
    int result = nums[0] + nums[1] + nums[2];

    for(int i=0;i<len-2;i++){
        int start = i+1;
        int end = len-1;
        while(start<end){
            int sum = nums[i] + nums[start] + nums[end];
            if(abs(target-sum)<abs(target-result)){
                result = sum;
            }
            if(sum>target){
                end--;
            } else if(sum<target){
                start++;
            } else{
                return result;
            }
        }
    }
    return result;
}


// 定义一个快排
void quickSort(vector<int> &nums, int left, int right) {
    int leftPos = left,rightPos = right;
    int pivot = nums[right];
    while (leftPos<rightPos){
        while(leftPos<rightPos&&nums[leftPos]<=pivot){
            leftPos++;
        }
        if(nums[leftPos]>pivot){
            nums[rightPos] = nums[leftPos];
            rightPos--;
        }
        while (leftPos<rightPos&&nums[rightPos]>=pivot){
            rightPos--;
        }
        if(nums[rightPos]<pivot){
            nums[leftPos] = nums[rightPos];
            leftPos++;
        }
    }
    nums[rightPos] = pivot;

    if (left<leftPos-1){
        quickSort(nums,left,leftPos-1);
    }

    if (right>rightPos+1){
        quickSort(nums,rightPos+1,right);
    }
};


Last Modified : 2020-07-20 15:50:27