当前位置: 首页 > news >正文

算法刷题之数组篇

题目一:两数之和

给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。

(注:返回的数组下标从1开始算起,保证target一定可以由数组里面2个数字相加得到)

方法一,双层for遍历:

不过,这种方法在牛客网上执行的时候报超时错误

import java.util.*;
public class Solution {/*** * @param numbers int整型一维数组 * @param target int整型 * @return int整型一维数组*/public int[] twoSum (int[] numbers, int target) {// write code hereint n = numbers.length;int[] res = {-1, -1};//遍历数组for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {//判断相加值是否为targetif (numbers[i] + numbers[j] == target) {res[0] = i+1;res[1] = j+1;//返回值return res;}}}return res;}
}

复杂度分析:

  • 时间复杂度:O(n^2) 遍历两次数组
  • 空间复杂度:O(1) 未申请额外空间

 方法二,hash表

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param numbers int整型一维数组* @param target int整型* @return int整型一维数组*/public int[] twoSum (int[] numbers, int target) {HashMap<Integer, Integer> map = new HashMap<>();//遍历数组for (int i = 0; i < numbers.length; i++) {if (map.containsKey(target - numbers[i])) {// 这里题目要求下标在数组中升序排列,这里这样放直接就满足了题意,因为数据A肯定先放入map,后面containsKey判断得出的数据B的下标i肯定大于数据A下标return new int[] {map.get(target - numbers[i]) + 1, i + 1};} else {map.put(numbers[i], i);}}throw new IllegalArgumentException("No solution");}
}

复杂度分析:

  • 时间复杂度:O(n) 一次遍历hash索引查找时间复杂度为O(1)
  • 空间复杂度:O(n) 申请了n大小的map空间

题目二:最接近的三数之和 

描述

给定一个数组 nums 和一个目标值 target ,请问从 nums 中选出三个数,使其之和尽量接近目标数,即三数之和与目标数只差绝对值尽可能小。

返回满足题面要求的三数之和。

数据范围:数组长度满足3≤n≤300  ,数组中的值满足 ∣nums[i]∣≤1000  ,目标值满足∣target∣≤10^4 ,可以保证只有一个结果。

 方法一,暴力三层循环

循环累加,计算三个数之和与目标值target差值绝对值最小

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param nums int整型一维数组 * @param target int整型 * @return int整型*/public int ClosestSum (int[] nums, int target) {// write code hereint sum_min = Integer.MAX_VALUE;int result=0;for(int i=0;i<nums.length-2;i++){for(int j=i+1;j<nums.length-1;j++){for(int k=j+1;k<nums.length;k++){int sum=nums[i]+nums[j]+nums[k];if(Math.abs(sum-target)<sum_min){sum_min=Math.abs(sum-target);result=sum;}}}}return result;}
}

方法二,先排序再循环 

数组在没有排序之前不容易实现某种算法,排序完之后,在固定第一个数字的情况下,通过与之后数据中头尾数据相加得sum,与target求差,循环比对差距大小。同时头尾数据会根据与target大小做调整,当sum>target时,尾数据下标-1,当sum<target时,头数据下标+1,sum=target,则可以直接返回。

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param nums int整型一维数组* @param target int整型* @return int整型*/public int ClosestSum (int[] nums, int target) {// write code here// 排序Arrays.sort(nums);// 记录结果int res = nums[0] + nums[1] + nums[2];for (int i = 0; i < nums.length - 2; i++) {// 头尾数据下标int start = i + 1;int end = nums.length - 1;while (start < end) {int sum = nums[i] + nums[start] + nums[end];//每次头尾数据变更之后,比对差值大小if (Math.abs(sum - target) < Math.abs(res - target)) {res = sum;}if (sum > target) {end--;} else if (sum < target) {start++;} else {return sum;}}}return res;}
}

相关文章:

算法刷题之数组篇

题目一&#xff1a;两数之和 给出一个整型数组 numbers 和一个目标值 target&#xff0c;请在数组中找出两个加起来等于目标值的数的下标&#xff0c;返回的下标按升序排列。 &#xff08;注&#xff1a;返回的数组下标从1开始算起&#xff0c;保证target一定可以由数组里面2…...

TR转发路由器测评—云企业网实现跨地域跨VPC的网络互通测评实战【阿里云产品测评】

文章目录 一.转发路由器 Transit Router 测评1.1 准备阶段1.2 本文测评收获1.3 什么是云企业网实例、转发路由器实例和云数据传输服务 二.使用云企业网实现跨地域跨VPC的网络互通2.2 **测试连通性**2.3 网络拓扑如下&#xff1a; 心得&#xff1a;总结&#xff1a; 声明&#x…...

1.1美术理论基础

一、光影 物体呈现在人们眼前的时候&#xff0c;不同的受光面其明暗变化以及物体的影子。 1.什么是黑白灰 在美术中黑白灰指亮面、灰面、暗面&#xff0c;属于素描的三大面&#xff0c;主要体验一个物体的整体寿光过程。普遍存在于各种艺术和设计领域。黑白灰作品的出现&#x…...

【Java 基础】21 多线程同步与锁

文章目录 1.存在的问题2.使用同步解决问题1) synchronized2) volatile3) 锁 总结 用多线程过程中&#xff0c;有可能出现 多个线程同时处理&#xff08;获取或修改等&#xff09;同一个数据&#xff0c;这个时候就 会发生数据不同步的问题&#xff0c; 因此出现了同步和锁来…...

Python语言基础知识(一)

文章目录 1、Python内置对象介绍2、标识符与变量3、数据类型—数字4、数据类型—字符串与字节串5、数据类型—列表、元组、字典、集合6、运算符和表达式7、运算符和表达式—算术运算符8、运算符和表达式—关系运算符9.1、运算符和表达式— 成员测试运算符in9.2、运算符和表达式…...

Xilinx FPGA平台DDR3设计详解(三):DDR3 介绍

本文介绍一下常用的存储芯片DDR3&#xff0c;包括DDR3的芯片型号识别、DDR3芯片命名、DDR3的基本结构等知识&#xff0c;为后续掌握FPGA DDR3的读写控制打下坚实基础。 一、DDR3芯片型​号 电路板上的镁光DDR3芯片上没有具体的型号名。 ​如果想知道具体的DDR3芯片型号&#…...

字典的遍历

字典不是有序的集合&#xff0c;就不能通过index来遍历了&#xff0c;那如何遍历字典呢? 方法一:直接用字典 for key in a_dict: print a_dict[key] 通过这样的结构可以的。 d {"liming" : 98, "wangli":95, "mali":90, "liping&q…...

Linux环境下的MySQL安装

文章目录 前提说明1.卸载内置环境2.检查系统安装包3.卸载这些默认安装包4.获取MySQL官方yum源5.安装MySQLyum源&#xff0c;对比前后yum源6.查看yum源是否生效7.安装MySQL服务8.查看相对应的配置文件9.启动服务10.查看启动服务11.登录方法一12.登录方法二13.登录方法三14.设置开…...

梦想与魔法:编程之路的挑战与荣耀

在年少轻狂的岁月里&#xff0c;我们都有过一些不切实际的梦想&#xff0c;渴望成为某种神奇的存在。我的梦想是成为一名神奇的码农&#xff0c;用键盘编织魔法&#xff0c;创造出炫酷的虚拟世界。然而&#xff0c;现实是残酷的&#xff0c;当我刚入门计算机领域时&#xff0c;…...

qt 5.15.2 主窗体菜单工具栏树控件功能

qt 5.15.2 主窗体菜单工具栏树控件功能 显示主窗体效果&#xff1a; mainwindow.h文件内容&#xff1a; #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include <QFileDialog> #include <QString> #include <QMessageBox>#inc…...

Day15——File类与IO流

1.java.io.File类的使用 1.1 File类的理解 File 类及本章下的各种流&#xff0c;都定义在 java.io 包下。一个 File 对象代表硬盘或网络中可能存在的一个文件或者文件目录&#xff08;俗称文件夹&#xff09;&#xff0c;与平台无关。&#xff08;体会万事万物皆对象&#xf…...

【Qt】QLineEdit显示输入十六进制,位数不足时按照规则填充显示及每两个字符以空格填充

问题 在实际开发中&#xff0c;有时候需要对输入进行限制&#xff0c;一是更加合理&#xff0c;二是防止出现误操作。 比如&#xff1a; 使用Qt进行应用程序开发时&#xff0c;对单行编辑框QLineEdit控件&#xff0c;设置只可输入十六进制。 限制输入的方式常用且经典的是使用…...

GPT 中文提示词技巧:参照 OpenAI 官方教程

前言 搜了半天什么 prompt engineering 的课&#xff0c;最后会发现 gpt 官方其实是有 prompt 教程的。因此本文主要是学习这篇教程。 概述 - OpenAI API 部分案例是参考&#xff1a;根据吴恩达老师教程总结出中文版prompt教程_哔哩哔哩_bilibili up主的内容。 一、尽可能清…...

原生微信小程序将字符串生成二维码图片

weapp-qrcode.js再最后 inde.ts中的内容 // pages/qrCode/index.ts // 引入weapp-qrcode.js文件 var QRCode require(../../utils/weapp-qrcode) Page({/*** 页面的初始数据*/data: {orderNo:"",imagePath:},/*** 生命周期函数--监听页面加载*/onLoad(options:any)…...

深入理解HTTPS加密协议

在现代网络环境中&#xff0c;数据安全和隐私保护至关重要。HTTPS&#xff08;全称为HyperText Transfer Protocol Secure&#xff09;是一种用于保障互联网通信安全的加密协议&#xff0c;它通过在HTTP协议的基础上添加SSL/TLS层来实现对数据的加密传输。本文将详细介绍HTTPS的…...

路径规划之PRM算法

系列文章目录 路径规划之Dijkstra算法 路径规划之Best-First Search算法 路径规划之A *算法 路径规划之D *算法 路径规划之PRM算法 路径规划之PRM算法 系列文章目录前言一、前期准备1.栅格地图2.采样3.路标 二、PRM算法1.起源2.流程3. 优缺点4. 实际效果 前言 之前提到的几种…...

深入理解数据在内存中是如何存储的,位移操作符如何使用(能看懂文字就能明白系列)文章超长,慢慢品尝

系列文章目录 C语言笔记专栏 能看懂文字就能明白系列 &#x1f31f; 个人主页&#xff1a;古德猫宁- &#x1f308; 信念如阳光&#xff0c;照亮前行的每一步 文章目录 系列文章目录&#x1f308; *信念如阳光&#xff0c;照亮前行的每一步* 前言引子一、2进制和进制转化为什么…...

ArcGIS提示当前许可不支持影像服务器

1、问题&#xff1a; 在用ArcGIS上处理影像栅格数据时&#xff08;比如栅格数据集裁剪、镶嵌数据集构建镶嵌线等&#xff09;经常会出现。 无法启动配置 RasterComander.ImageServer <详信息 在计算机XXXXX上创建服务器对象实例失败 当前许可不支持影像服务器。 ArcGIS提示当…...

Android P 9.0 增加以太网静态IP功能

效果图 一、Settings添加以太网的配置&#xff1a; 1、vendor\mediatek\proprietary\packages\apps\MtkSettings\res\xml\network_and_internet.xml <com.android.settingslib.RestrictedPreferenceandroid:key"ethernet_settings"android:title"string/et…...

Android12之MediaCodec硬编解码调试手段(四十九)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...