16. 3Sum Closest

题目描述和难度

• 题目描述：

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

• 题目难度：中等。
• 英文网址：16. 3Sum Closest 。
• 中文网址：16. 最接近的三数之和 。

思路分析

求解关键：这道题和二分查找没有什么关系，就是双指针对撞，前提是要先将数组排序。

参考解答

参考解答1

Python 写法：

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """

        if len(nums) < 3:
            return []
        # 初始化
        diff = float('inf')
        nums.sort()
        for index in range(len(nums) - 2):
            if index > 0 and nums[index] == nums[index - 1]:
                continue
            l = index + 1
            r = len(nums) - 1
            while l < r:
                s = nums[index] + nums[l] + nums[r]
                if abs(s - target) < diff:
                    diff = abs(s - target)
                    res = s
                if s > target:
                    r -= 1
                elif s < target:
                    l += 1
                else:
                    return target
        return res


if __name__ == '__main__':
    nums = [-1, 0, 1, 1, 55]
    target = 3
    solution = Solution()
    result = solution.threeSumClosest(nums, target)
    print(result)

Java 写法：

import java.util.Arrays;

/**
 * 这道题和二分查找没有什么关系，就是双指针对撞
 */
public class Solution {

    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        if (len < 3) {
            throw new IllegalArgumentException("参数错误");
        }
        // 初始化

        int diff = Integer.MAX_VALUE;
        int res = nums[0] + nums[1] + nums[len - 1];
        // 排序很关键
        Arrays.sort(nums);
        // len-3 len-2 len-1
        for (int i = 0; i < len - 2; i++) {
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    return target;
                }
                if (Math.abs(sum - target) < diff) {
                    diff = Math.abs(sum - target);
                    res = sum;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 2, 1, -4};
        int target = 1;
        Solution solution = new Solution();
        int threeSumClosest = solution.threeSumClosest(nums, target);
        System.out.println(threeSumClosest);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0016-3sum-closest ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。