Leecode-016-最接近的三数之和

思路：排序+双指针

• 本题目和Leetcode-015合在一起是三数之和的系列题目
• https://leetcode-cn.com/problems/3sum/（Leetcode-015）

题目描述

• 给定一个包括 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(nlogn)
• 在数组 nums 中，进行遍历，每次遍历固定一个nums[i]
• 其次使用两个指针，一个L指针指向i + 1 处，一个R指针指向 nums.length-1 处，也就是结尾处。
• 计算sum的值 ，sum = nums[i] + nums[L] + nums[R]
• 最后判断sum 和 target的关系，因为数组有序，
  • 如果sum > target, R --
  • 如果sum < target , L++
  • 如果 sum == target ,距离为0直接返回结果

举个例子：

1. 排序

2. 初始化

3. for循环

class Solution {
    public int threeSumClosest(int[] nums, int target) {

        // 1. 排序
        Arrays.sort(nums);


        // 2. 初始化
        int ans = nums[0] + nums[1] + nums[2];



        // 3. 循环固定nums[i]
        for (int i = 0; i < nums.length; i++) {
            int L = i + 1;
            int R = nums.length - 1;

            while (L < R){
                // 三数之和
                int sum = nums[i] + nums[L] + nums[R];

                // 每次更新结果
                if (Math.abs(target - sum) < Math.abs(target - ans)){
                    ans = sum;
                }

                // 判断sum 和 target之间的关系
                if (sum > target){
                    R--;
                }else if (sum < target){
                    L++;
                }else {
                    return ans;
                }
            }
        }
        return ans;
    }
}

复杂度分析：

• 时间复杂度 ：O（n^2） 排序O(nlogn) + 遍历O(n^2) = O(n^2)
• 空间复杂度： O(1) 没有使用额外的空间。

打赏