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

embedded/2024/11/29 19:29:07/

问题描述

在这里插入图片描述


思路分析

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/embedded/141556.html

相关文章

(附项目源码可免费领取)java开发语言,springboot宿舍管理系统_574,计算机毕设程序开发+文案(LW+PPT)

摘 要 近些年来&#xff0c;随着科技的飞速发展&#xff0c;互联网的普及逐渐延伸到各行各业中&#xff0c;给人们生活带来了十分的便利&#xff0c;宿舍管理系统利用计算机网络实现信息化管理&#xff0c;使整个宿舍管理的发展和服务水平有显著提升。 本文拟采用java技术和Sp…

【机器学习】—逻辑回归

逻辑回归实现详解 介绍 逻辑回归&#xff08;Logistic Regression&#xff09;是一种广泛应用于分类问题的统计模型&#xff0c;尤其适用于二分类问题。本文将通过一个简单的例子&#xff0c;使用Python和PyTorch库实现逻辑回归&#xff0c;并通过可视化展示模型的训练过程和…

Sofia-SIP 使用教程

Sofia-SIP 是一个开源的 SIP 协议栈&#xff0c;广泛用于 VoIP 和即时通讯应用。以下是一些基本的使用教程&#xff0c;帮助你快速上手 Sofia-SIP。 1. 安装 Sofia-SIP 首先&#xff0c;你需要安装 Sofia-SIP 库。你可以从其官方 GitHub 仓库克隆源代码并编译安装&#xff1a…

CodeIgniter URL结构

CodeIgniter 的URL 结构设计得简洁且易于管理。通常遵循以下模式&#xff1a; http://<domain>/<index_page>/<controller>/<method>/<parameters> 下面是每个部分的详细说明&#xff1a; <domain>&#xff1a; 这是你的网站域名&#…

HTML CSS JS基础考试题与答案

一、选择题&#xff08;2分/题&#xff09; 1&#xff0e;下面标签中&#xff0c;用来显示段落的标签是&#xff08; d &#xff09;。 A、<h1> B、<br /> C、<img /> D、<p> 2. 网页中的图片文件位于html文件的下一级文件夹img中&#xff0c;…

Python中的map函数

Python中的map函数是一种常用的高雅实现&#xff0c;它能够在不使用第三方库的情况下对一个列表进行映射&#xff0c;并返回一个新的列表。map函数不仅能够提高Python代码的可读性&#xff0c;还能够拓展Python的功能&#xff0c;使其成为一种强大的数据处理工具。 Python中的…

Vue3+node.js实现注册

文章目录 前端代码实现后端代码实现 效果图 前端代码实现 <template><div class"register-container"><el-card class"register-card"><template #header><div class"card-header"><span>注册</span&…

林业产品推荐系统:Spring Boot开发手册

3 系统分析 这部分内容虽然在开发流程中处于最开始的环节&#xff0c;但是它对接下来的设计和实现起着重要的作用&#xff0c;因为系统分析结果的好坏&#xff0c;将直接影响后面环节的开展。 3.1可行性研究 影响系统开发的因素有很多&#xff0c;比如开发成本高就不适合开展&a…