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

豆包MarsCode算法题:三数之和问题

问题描述

在这里插入图片描述


思路分析

1. 排序数组

  • 目的: 将数组 arr 按升序排序,这样可以方便地使用双指针找到满足条件的三元组,同时避免重复的三元组被重复计算。
  • 优势:
    • 数组有序后,处理两个数和 target - arr[i] 的问题可以通过双指针快速找到所有可能的组合。

2. 使用双指针寻找目标对

  • 核心思路:
    • 对于每个固定的元素 a = arr[i] ,寻找剩下的两个元素 b , c 使得 a + b + c = target ,即 b + c = target - a
    • leftright 分别指向当前子数组的起点和终点(i + 1arr.length - 1),通过比较 arr[left] + arr[right]target - arr[i] 的大小调整指针:
      • 如果 arr[left] + arr[right] < target - arr[i] ,说明需要更大的数,移动 left
      • 如果 arr[left] + arr[right] > target - arr[i] ,说明需要更小的数,移动 right
      • 如果两者相等,记录满足条件的对,并继续移动指针。

3. 处理重复元素

在满足条件时,需要仔细处理 arr[left]arr[right] 的重复计数:

  • 情况1: 如果 arr[left] != arr[right]
    • 统计所有重复的 arr[left]arr[right] 的数量,假设重复次数分别为 countLeftcountRight,则可以形成的三元组数为 countLeft × countRight
  • 情况2: 如果 arr[left] == arr[right]
    • 说明所有元素都相等,假设重复次数为 n,则可以形成的三元组数为:

在这里插入图片描述

  • n 表示元素的重复次数。
  • (n−1) 是从剩余元素中选择的方式数。

4. 结果取模

由于结果可能非常大,每次更新结果时都需要对 10⁹ + 7 取模,避免溢出。

算法复杂度

  • 时间复杂度:时间复杂度为 O(n²)
  • 空间复杂度: 只使用了常数级的额外空间,复杂度为 O(1)

参考代码(Java)

import java.util.Arrays;public class Main {public static int solution(int[] arr, int t) {int MOD = 1_000_000_007;Arrays.sort(arr); // 排序int n = arr.length;long count = 0;for (int i = 0; i < n - 2; i++) {int target = t - arr[i];int left = i + 1, right = n - 1;while (left < right) {if (arr[left] + arr[right] == target) {if (arr[left] == arr[right]) { // 如果左指针和右指针值相同int num = right - left + 1;count += (long) num * (num - 1) / 2; // 组合数C(num, 2)count %= MOD;break;} else { // 如果左指针和右指针值不同int leftCount = 1, rightCount = 1;// 统计左指针相同值的个数while (left + 1 < right && arr[left] == arr[left + 1]) {left++;leftCount++;}// 统计右指针相同值的个数while (right - 1 > left && arr[right] == arr[right - 1]) {right--;rightCount++;}// 累加计数count += (long) leftCount * rightCount;count %= MOD;left++;right--;}} else if (arr[left] + arr[right] < target) {left++;} else {right--;}}}return (int) count;}public static void main(String[] args) {System.out.println(solution(new int[]{1, 1, 2, 2, 3, 3, 4, 4, 5, 5}, 8) == 20);System.out.println(solution(new int[]{2, 2, 2, 2}, 6) == 4);System.out.println(solution(new int[]{1, 2, 3, 4, 5}, 9) == 2);System.out.println(solution(new int[]{1, 1, 1, 1}, 3) == 4);}
}

代码分析

1. 排序和初始化

Arrays.sort(arr); // 排序
int n = arr.length;
long count = 0;
  • 作用:
    • 对数组进行升序排序,使双指针查找两个数的和时能够利用有序性快速调整指针。
    • 初始化 count 用于累计满足条件的三元组数量。

2. 遍历数组

for (int i = 0; i < n - 2; i++) {int target = t - arr[i];int left = i + 1, right = n - 1;
}
  • 作用:
    • 遍历数组的每个元素 arr[i],将其固定为三元组的第一个数 a
    • 计算剩下两个数的目标和 target = t - arr[i]
    • 设置双指针,lefti + 1 开始,right 从数组末尾开始。
  • 边界条件:
    • 由于需要三个不同的数,循环只需要到 n - 2
    • 避免越界错误。

3. 双指针查找两数之和

while (left < right) {if (arr[left] + arr[right] == target) {...} else if (arr[left] + arr[right] < target) {left++;} else {right--;}
}
  • 核心逻辑:
    • arr[left] + arr[right] == target :
      • 找到一组满足条件的对,需要进一步统计并更新结果。
    • arr[left] + arr[right] < target :
      • 总和太小,增加 left 指针以尝试增大总和。
    • arr[left] + arr[right] > target :
      • 总和太大,减小 right 指针以尝试减小总和。

4. 处理双指针值相同的情况

if (arr[left] == arr[right]) { // 左右值相同int num = right - left + 1;count += (long) num * (num - 1) / 2; // 组合数C(num, 2)count %= MOD;break;
}
  • 逻辑:
    • 如果 arr[left] == arr[right],说明所有元素都相等,从中选择两个的组合数为 C(num, 2) = num × (num - 1) / 2
    • 直接更新 count,退出当前循环。

5. 处理双指针值不同的情况

int leftCount = 1, rightCount = 1;// 统计左指针相同值的个数
while (left + 1 < right && arr[left] == arr[left + 1]) {left++;leftCount++;
}// 统计右指针相同值的个数
while (right - 1 > left && arr[right] == arr[right - 1]) {right--;rightCount++;
}// 累加计数
count += (long) leftCount * rightCount;
count %= MOD;left++;
right--;
  • 逻辑:
    • 统计重复值:
      • 使用两个循环分别统计 arr[left]arr[right] 的重复次数。
    • 组合方式:
      • 如果 arr[left]arr[right] 值不同,则可以形成 leftCount × rightCount 对满足条件的组合。
    • 更新 count 并对结果取模,防止溢出。

6. 结果返回

return (int) count;
  • 将结果转换为 int 并返回,确保符合题目要求。

相关文章:

豆包MarsCode算法题:三数之和问题

问题描述 思路分析 1. 排序数组 目的: 将数组 arr 按升序排序&#xff0c;这样可以方便地使用双指针找到满足条件的三元组&#xff0c;同时避免重复的三元组被重复计算。优势: 数组有序后&#xff0c;处理两个数和 target - arr[i] 的问题可以通过双指针快速找到所有可能的组…...

【Android】AnimationDrawable帧动画的实现

目录 引言 一、AnimationDrawable常用方法 1.1 导包 1.2 addFrame 1.3 setOneShot 1.4 start 1.5 stop 1.6 isRunning 二、 从xml文件获取并播放帧动画 2.1 创建XML文件 2.2 在布局文件中使用帧动画资源 三、在代码中生成并播放帧动画 3.1 addFrame加入帧动画列…...

【消息序列】详解(7):剖析回环模式--设备测试的核心利器

目录 一、概述 1.1. 本地回环模式 1.2. 远程环回模式 二、本地回环模式&#xff08;Local Loopback mode&#xff09; 2.1. 步骤 1&#xff1a;主机进入本地环回模式 2.2. 本地回环测试 2.2.1. 步骤 2a&#xff1a;主机发送HCI数据包并接收环回数据 2.2.2. 步骤 2b&…...

解决Ubuntu 22.04系统中网络Ping问题的方法

在Ubuntu 22.04系统中&#xff0c;网络问题时有发生&#xff0c;尤其是当涉及到静态IP地址配置和网线直连的两台机器时。本文将探讨一种常见问题——断开并重新连接网线后&#xff0c;尽管网卡显示为UP状态&#xff0c;但无法立即ping通对方机器&#xff0c;以及如何解决这一问…...

【大数据学习 | Spark-SQL】Spark-SQL编程

上面的是SparkSQL的API操作。 1. 将RDD转化为DataFrame对象 DataFrame&#xff1a; DataFrame是一种以RDD为基础的分布式数据集&#xff0c;类似于传统数据库中的二维表格。带有schema元信息&#xff0c;即DataFrame所表示的二维表数据集的每一列都带有名称和类型。这样的数…...

15分钟做完一个小程序,腾讯这个工具有点东西

我记得很久之前&#xff0c;我们都在讲什么低代码/无代码平台&#xff0c;这个概念很久了&#xff0c;但是&#xff0c;一直没有很好的落地&#xff0c;整体的效果也不算好。 自从去年 ChatGPT 这类大模型大火以来&#xff0c;各大科技公司也都推出了很多 AI 代码助手&#xff…...

manim动画编程(安装+入门)

文章目录 1.基本介绍2.效果展示3.安装步骤3.1安装manba软件3.2配置环境变量3.3查看是否成功3.4什么是mamba3.5创建虚拟环境3.6尝试进入虚拟环境 4.vscode操作4.1默认配置文件 5.安装ffmpeg6.安装manim软件6.vscode制作7.我的学习收获 1.基本介绍 这个manim就是一款软件&#x…...

STL算法之数值算法<stl_numeric.h>

这一节介绍的算法&#xff0c;统称为数值(numeric)算法。STL规定&#xff0c;欲使用它们&#xff0c;客户端必须包含头文件<numeric>.SGI将它们实现与<stl_numeric.h>文件中。 目录 运用实例 accumulate adjacent_difference inner_product partial_sum pow…...

Oracle如何记录登录用户IP

在运维场景中&#xff0c;在定位到某个SQL引起系统故障之后&#xff0c;想知道是哪台机器发过来的&#xff0c;方便定位源头&#xff0c;该如何解决&#xff1f; 在 Oracle 数据库中记录登录用户的 IP 地址可以通过多种方法实现。以下是几种常见的方法&#xff0c;包括使用触发…...

Python图像处理:打造平滑液化效果动画

液化动画中的强度变化是通过在每一帧中逐渐调整液化效果的强度参数来实现的。在提供的代码示例中&#xff0c;强度变化是通过一个简单的线性插值方法来控制的&#xff0c;即随着动画帧数的增加&#xff0c;液化效果的强度也逐渐增加。 def liquify_image(image, center, radius…...

构建Ceph分布式文件共享系统:手动部署指南

#作者:西门吹雪 文章目录 micro-Services-TutorialCeph分布式文件共享方案部署Ceph集群使用CephCeph在kubernetes集群中的使用 micro-Services-Tutorial 微服务最早由Martin Fowler与James Lewis于2014年共同提出&#xff0c;微服务架构风格是一种使用一套小服务来开发单个应…...

数据结构——用数组实现栈和队列

目录 用数组实现栈和队列 一、数组实现栈 1.stack类 2.测试 二、数组实现队列 1.Queue类 2.测试 查询——数组&#xff1a;数组在内存中是连续空间 增删改——链表&#xff1a;链表的增删改处理更方便一些 满足数据先进后出的特点的就是栈&#xff0c;先进先出就是队列…...

vue3typescript,shims-vue.d.ts中declare module的vue声明

webpack已经有了vue-loader这些loader了&#xff0c;为什么还需要declare module *.vue’呢&#xff1f; declare module 是为了告诉 tsc 这是一个“模块”。 如果不声明&#xff0c; IDE 里因为 tsc 类型检查&#xff0c; lint 会标红。 但vue-loader 是在 Webpack 构建阶段使…...

C/C++基础知识复习(30)

1) 什么是 C 中的 Lambda 表达式&#xff1f;它的作用是什么&#xff1f; Lambda 表达式&#xff1a; 在 C 中&#xff0c;Lambda 表达式是一种可以定义匿名函数的机制&#xff0c;可以在代码中快速创建一个内联的函数对象&#xff0c;而不需要显式地定义一个函数。Lambda 表…...

【NLP 1、人工智能与NLP简介】

人人都不看好你&#xff0c;可偏偏你最争气 —— 24.11.26 一、AI和NLP的基本介绍 1.人工智能发展流程 弱人工智能 ——> 强人工智能 ——> 超人工智能 ① 弱人工智能 人工智能算法只能在限定领域解决特定的问题 eg&#xff1a;特定场景下的文本分类、垂直领域下的对…...

网络安全事件管理

一、背景 信息化技术的迅速发展已经极大地改变了人们的生活&#xff0c;网络安全威胁也日益多元化和复杂化。传统的网络安全防护手段难以应对当前繁杂的网络安全问题&#xff0c;构建主动防御的安全整体解决方案将更有利于防范未知的网络安全威胁。 国内外的安全事件在不断增…...

Swagger记录一次生成失败

最近在接入Swagger的时候遇到一个问题&#xff0c;就是Swagger UI可以使用的&#xff0c;但是/v3/docs 这个接口的json返回的base64类型的json&#xff0c;并不是纯json&#xff0c;后来检查之后是因为springboot3里面配置了json压缩。 Beanpublic HttpMessageConverters cusHt…...

Go 语言常用工具方法总结

在 Go 语言开发中&#xff0c;常常需要进行一些常见的类型转换、字符串处理、时间处理等操作。本文将总结一些常用的工具方法&#xff0c;帮助大家提高编码效率&#xff0c;并提供必要的代码解释和注意事项&#xff08;go新人浅浅记录一下&#xff0c;以后来翻看&#x1f923;&…...

ThingsBoard规则链节点:GCP Pub/Sub 节点详解

目录 引言 1. GCP Pub/Sub 节点简介 2. 节点配置 2.1 基本配置示例 3. 使用场景 3.1 数据传输 3.2 数据分析 3.3 事件通知 3.4 任务调度 4. 实际项目中的应用 4.1 项目背景 4.2 项目需求 4.3 实现步骤 5. 总结 引言 ThingsBoard 是一个开源的物联网平台&#xff0…...

【Linux】select,poll和epoll

select&#xff0c;poll&#xff0c;epoll都是IO多路复用的机制。I/O多路复用就通过一种机制&#xff0c;可以监视多个描述符fd&#xff0c;一旦某个描述符就绪(一般是读就绪或者写就绪)&#xff0c;系统会通知有I/O事件发生了&#xff08;不能定位是哪一个&#xff09;。但sel…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...