当前位置: 首页 > 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…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

设计模式和设计原则回顾

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

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...