leetcode - [16] 3Sum Closest

2020/07/20

问题描述

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.

从整数数组中找出三个数,使其和最接近目标值target

举个例子:

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

类似题:

[15] 3Sum

解法1

老规矩,使用双指针思想。

先使用一个变量i从头至尾遍历整个数组,注意重复的元素,在此过程中,

使用lr两个指针,计算三者元素和与目标值target的最小差。

来看下实现:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0x3f3f3f3f;
        for (int i = 0; i < n; i++){
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = n - 1;
            while (l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if (Math.abs(sum - target) < Math.abs(ans - target)){
                    ans = sum;
                }
                if (sum == target){
                    return ans;
                } else if (sum < target){
                    l++;
                } else {
                    r--;
                }
            }
        }
        return ans;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory