JAVA 牛牛

16. 最接近的三数之和

  • May 20, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法： 数组遍历 双指针
  • 思路： 数组遍历 双指针
  • 类似题型:

题目 16. 最接近的三数之和

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

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

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

方法一 双指针

  • 解题思路：
    • 左右指针向中间移动，中间同时从左向右移动 i，并三数相加
    • 通过每次 三数之和 - 目标值 ，比较绝对值
  • 复杂度分析:
    • 时间复杂度 $O(N^2)$ ，$N$ 为数组的长度
    • 空间复杂度 $O(1)$

python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums_len = len(nums)
        nums.sort()
        ans_sum = nums[0] + nums[1] + nums[2];
        for i in range(nums_len):
            left, right = i + 1 , nums_len - 1
            while left < right:
                curr_sum = nums[i] + nums[left] + nums[right]
                if abs(curr_sum - target) < abs(ans_sum - target):
                    ans_sum = curr_sum
                if curr_sum > target: right -= 1
                elif curr_sum < target: left += 1
                else: return target
        return ans_sum

java

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int nums_len = nums.length;
        Arrays.sort(nums);
        int ans_sum = nums[0] + nums[1] + nums[2];
        for(int i = 0 ;i<nums_len;i++) {
            int left = i + 1, right = nums_len - 1;
            while (left < right) {
                int curr_sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(curr_sum - target) < Math.abs(ans_sum - target) )
                    ans_sum = curr_sum;
                if (curr_sum > target) right --;
                else if (curr_sum < target) left ++;
                else return target;
            }
        }
        return ans_sum;
    }
}
  • 如果你觉得本文对你有帮助，请点赞👍支持
  • 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出
Search