最接近的三数之和

发布于:2024-07-11 ⋅ 阅读:(17) ⋅ 点赞:(0)

文章目录

题目

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。

示例 1:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2:

输入:nums = [0,0,0], target = 1
输出:0

提示:

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

Related Topics

  • 数组
  • 双指针
  • 排序

代码

基本思路是首先对数组进行排序,然后遍历数组中的每个元素作为三个数中的第一个数(记作nums[i]),使用双指针法来寻找后面两个数(记作nums[l]和nums[r]),使得这三个数的和尽可能接近目标值target。

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 1. 排序,默认升序排列
        nums = Arrays.stream(nums).sorted().toArray();
        System.out.println("nums = " + Arrays.toString(nums));
        int len= nums.length, result = 99999;
        // 2. 遍历数组,固定数 i
        for (int i = 0; i < len; i++) {
            // 3. 定义双指针,左指针 l=i+1,右指针 r=len-1
            int l = i + 1, r = len - 1;
            // 4. 双指针搜索,求和
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                // 5. 与目标值比较
                // a.相等,直接return
                if (sum == target) {
                    return sum;
                }
                // 6. 需要一个temp记录当前的差值
                if (Math.abs(sum - target) < Math.abs(result - target))  {
                    result = sum;
                }
                // b.更小,则需要更大
                if (sum < target){
                    l++;
                }
                // c.更大,则需要更小
                else {
                    r--;
                }
            }
        }
        return result;
    }
}

在这里插入图片描述

优化思路

解题步骤:

  1. 排序
  2. 遍历数组
  3. 双指针搜索
  4. 求和比较

时间复杂度分析:

  1. 排序:使用 Arrays.stream(nums).sorted().toArray() 对数组进行排序。这部分的时间复杂度是 O(n log n)
  2. 遍历数组:使用一个for循环。这部分的时间复杂度是 O(n)
  3. 双指针遍历:遍历次数为i+1→n,外嵌一个for循环。因此时间复杂度为O(n^2);
  4. 求和比较的时间复杂度也是O(n);
    因此,整体时间复杂度=O(n^2)

优化方向:
1.减少重复遍历次数
2.优化排序算法

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int len= nums.length, result = 99999;
        // 1. 排序,默认升序排列
        // 优化2:排序算法
        sort(nums, 0, len-1);
        System.out.println("nums = " + Arrays.toString(nums));
        // 2. 遍历数组,固定数 i
        for (int i = 0; i < len; i++) {
            // 优化1:减少重复遍历的次数
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 3. 定义双指针,左指针 l=i+1,右指针 r=len-1
            int l = i + 1, r = len - 1;
            // 4. 双指针搜索,求和
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                // 5. 与目标值比较
                // a.相等,直接return
                if (sum == target) {
                    return sum;
                }
                // 6. 需要一个temp记录当前的差值
                if (Math.abs(sum - target) < Math.abs(result - target))  {
                    result = sum;
                }
                // b.更小,则需要更大
                if (sum < target){
                    l++;
                }
                // c.更大,则需要更小
                else {
                    r--;
                }
            }
        }
        return result;
    }
    public void sort(int[] nums,int start,int end){
        if (start<end){
            int p = partition(nums,start,end);
            sort(nums,start,p-1);
            sort(nums,p+1,end);
        }
    }
    public int partition(int[] nums,int start,int end){
        int pivot = nums[end];
        int pi = start;
        for (int i = start; i < end; i++) {
            if (nums[i] <= pivot){
                swap(nums,pi,i);
                pi++;
            }
        }
        swap(nums,pi,end);
        return pi;
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

在这里插入图片描述