萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣第16题-最接近的三数之和

发表于 2022-03-30 | 分类于 力扣刷题 | 0 | 阅读次数 117

题目描述

给你一个长度为 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
-10^4 <= target <= 10^4

题目评估

知识点:数组、双指针、排序
官方难度:中等

分析

本体思虑和上一题(三数之和)类似,只不过是把和换成了最接近的一个数。

Java代码题解

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int res = nums[0] + nums[1] + nums[2];
        // 从小到大排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 第一个数字去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 计算二指针和三指针
            int j = i + 1;
            int k = nums.length - 1;
            // 双指针遍历
            while (j < k) {
                // 求和
                int sum = nums[i] + nums[j] + nums[k];
                // 等于目标直接返回
                if (sum == target) {
                    return sum;
                }
                // 计算
                if (Math.abs(sum - target) < Math.abs(res - target)) {
                    // 更换最接近的结果
                    res = sum;
                }
                if (sum > target) {
                    // 和大于目标值,和需要减小,左移三指针
                    do {
                        k--;
                    } while (j < k && nums[k] == nums[k + 1]);
                } else {
                    // 和小于等于目标值,和需要增加,右移二指针
                    do {
                        j++;
                    } while (j < k && nums[j] == nums[j - 1]);
                }
            }
        }
        return res;
    }

}

复杂度分析

时间复杂度:O(N^2),其中 N 是数组 nums 的长度。我们首先需要O(NlogN) 的时间对数组进行排序,随后在枚举的过程中,使用一重循环 O(N) 枚举 a,双指针 O(N) 枚举 b 和 c,故一共是 O(N^2)。
空间复杂度:O(logN)。排序需要使用 O(logN) 的空间。然而我们修改了输入的数组 nums,在实际情况下不一定允许,因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序,此时空间复杂度为 O(N)。

# 算法 # 程序设计 # 力扣
力扣第15题-三数之和
力扣第19题-删除链表的倒数第N个节点
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持