萤火小屋

优律的知识库

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

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

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

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

题目描述

给你一个长度为 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个节点
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

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