[LeetCode] 16. 3Sum Closest 最近三数之和

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 16. 3Sum Closest 最近三数之和,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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.html

Example:java

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

15. 3Sum 三数之和 的拓展,这题是让找到和目标数最接近的数字组合,仍是用3Sum的方法,遍历每一个数,对剩余数组进行双指针扫描,只是此次要设一个变量minDiff来记录最小差值的绝对值,若是当前三数的和与目标数相等,直接返回三数和。若是三数和与目标数的差的绝对值小于minDiff,则此组合更接近目标数,result变为此组合的和,迭代查找直到结束, 返回result。python

Java:数组

public class Solution {
    /**
    * @param numbers: Give an array numbers of n integer
    * @param target : An integer
    * @return : return the sum of the three integers, the sum closest target.
    */  
    public int threeSumClosestV2(int[] numbers,int target) {
        if (numbers == null || numbers.length < 3) {
            return Integer.MAX_VALUE;
        }

        Arrays.sort(numbers);

        int length = numbers.length;
        int closest = Integer.MAX_VALUE / 2;

        for (int i = 0; i < length - 2; i++) {
            int pl = i + 1;
            int pr = length - 1;

            while (pl < pr) {
                int sum = numbers[i] + numbers[pl] + numbers[pr];
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    pl++;
                } else {
                    pr--;
                }
                closest = Math.abs(sum - target) < Math.abs(closest - target) ?
                        sum : closest;
            }
        }
        return closest;
    }
}

 Python:post

class Solution(object):
    def threeSumClosest(self, nums, target):
        nums, result, min_diff, i = sorted(nums), float("inf"), float("inf"), 0
        while i < len(nums) - 2:
            if i == 0 or nums[i] != nums[i - 1]:
                j, k = i + 1, len(nums) - 1
                while j < k:
                    diff = nums[i] + nums[j] + nums[k] - target
                    if abs(diff) < min_diff:
                        min_diff = abs(diff)
                        result = nums[i] + nums[j] + nums[k]
                    if diff < 0:
                        j += 1
                    elif diff > 0:
                        k -= 1
                    else:
                        return target
            i += 1
        return result

C++:url

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        if(num.size()<3) return INT_MAX;
        sort(num.begin(),num.end());
        int minDiff = INT_MAX;
        for(int i=0; i<num.size()-2; i++) {
            int left=i+1, right = num.size()-1;
            while(left<right) {
                int diff = num[i]+num[left]+num[right]-target;
                if(abs(diff)<abs(minDiff)) minDiff = diff;
                if(diff==0) 
                    break;
                else if(diff<0)
                    left++;
                else
                    right--;
            }
        } 
        return target+minDiff;
    }
};

  

相似题目:指针

[LeetCode] 15. 3Sum 三数之和code

[LeetCode] 259. 3Sum Smaller 三数之和较小值htm

 

All LeetCode Questions List 题目汇总