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

news/2024/11/29 20:21:30/

问题描述

在这里插入图片描述


思路分析

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)

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. 排序和初始化

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

2. 遍历数组

java">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. 双指针查找两数之和

java">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. 处理双指针值相同的情况

java">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. 处理双指针值不同的情况

java">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. 结果返回

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

http://www.ppmy.cn/news/1550979.html

相关文章

JAVA项目-------医院挂号系统

1&#xff0c;项目目的 1、科室管理&#xff1a;新增科室&#xff0c;删除科室&#xff08;如果有医生在&#xff0c;则不能删除该科室&#xff09;&#xff0c;修改科室。 2、医生管理&#xff1a;录入医生信息&#xff0c;以及科室信息。修改医生信息&#xff08;主要是修改…

【AI系统】分布式通信与 NVLink

分布式通信与 NVLink 在进入大模型时代后&#xff0c;大模型的发展已成为 AI 的核心&#xff0c;但训练大模型实际上是一项比较复杂的工作&#xff0c;因为它需要大量的 GPU 资源和较长的训练时间。 此外&#xff0c;由于单个 GPU 工作线程的内存有限&#xff0c;并且许多大模…

ODB 框架

目录 概述 基本工作原理 映射C对象到数据库表 从数据库中加载对象 持久化C对象到数据库 ODB常用接口 表创建预处理 #pragma db Object table 数据表属性 id auto column&#xff08;“xxx”&#xff09; type("xxx") unique index null default&…

Github 基本使用学习笔记

1. 基本概念 1.1 一些名词 Repository&#xff08;仓库&#xff09; 用来存放代码&#xff0c;每个项目都有一个独立的仓库。 Star&#xff08;收藏&#xff09; 收藏你喜欢的项目&#xff0c;方便以后查看。 Fork&#xff08;克隆复制项目&#xff09; 复制别人的仓库&…

【力扣热题100】—— Day3.相交链表

被你改变的那部分我&#xff0c;代替你&#xff0c;永远与我站在一起 —— 24.11.28 160. 相交链表 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 …

连续变量的 交叉熵 如何计算 python tensorflow

连续变量的交叉熵通常在机器学习中的回归问题中使用&#xff0c;但它也可以用于分类问题&#xff0c;当概率分布是连续的时。连续变量的交叉熵计算公式如下&#xff1a; 设 \( p(x) \) 是真实概率密度函数&#xff0c;\( q(x) \) 是预测概率密度函数&#xff0c;交叉熵 \( H(p…

ELK配置索引清理策略

在ELFK&#xff08;Elasticsearch, Logstash,Filebeat, Kibana&#xff09;堆栈中配置索引清理策略是一个常见的需求&#xff0c;因为日志数据会随着时间的推移而积累&#xff0c;占用大量的存储空间。以下是一些配置索引清理策略的方法&#xff1a; 1. 使用索引生命周期管理&…

Linux操作系统2-进程控制3(进程替换,exec相关函数和系统调用)

上篇文章&#xff1a;Linux操作系统2-进程控制2(进程等待&#xff0c;waitpid系统调用&#xff0c;阻塞与非阻塞等待)-CSDN博客 本篇代码Gitee仓库&#xff1a;Linux操作系统-进程的程序替换学习 d0f7bb4 橘子真甜/linux学习 - Gitee.com 本篇重点&#xff1a;进程替换 目录 …