如何高效解决含重复元素的 Two Sum 问题(返回所有索引对)

小婷同学_7263

小婷同学_7263

2026-01-17

750人浏览

原创

如何高效解决含重复元素的 Two Sum 问题(返回所有索引对)

本文详解如何修改传统 two sum 解法,使其支持数组中存在重复元素的情况(如 [3,2,3]、target=6),并正确返回所有满足条件的索引对组合,兼顾时间效率与结果完整性。

在标准 Two Sum 问题中,若数组元素唯一且只需返回一对索引(如 LeetCode #1),常用哈希表一次遍历即可实现 O(n) 时间复杂度。但当输入含重复值(如 [3, 2, 3])且目标为 6 时,原逻辑易遗漏 nums[0] + nums[2] === 6 这一有效解——因为简单哈希映射通常只保存某值的最后一个索引,导致早期出现的相同值被覆盖。

你的初始实现 nums.at(index + 1) 仅检查相邻元素,本质是 O(n) 的暴力近似,既无法处理非相邻重复(如 [3,2,3] 中索引 0 和 2),也无法扩展至多解场景,因此不适用于通用 Two Sum。

✅ 推荐方案:哈希表存储值 → 索引数组映射
核心思想:用 Map 记录每个数值出现的所有索引。遍历过程中,对当前元素 ele 计算补数 complement = target - ele;若该补数已存在于 Map 中,则将 所有已记录的补数索引 与当前索引 index 组合成 [compIndex, index],加入结果集。最后将当前 ele 的索引追加到其对应索引数组中(即使已存在,也要保留全部位置)。

该方案时间复杂度仍为 O(n)(单次遍历,Map 操作均摊 O(1)),空间复杂度 O(n),且天然支持任意数量重复元素与全部解的枚举。

AdsTurbo AI
AdsTurbo AI

AdsTurbo AI是一款AI文本写作工具,AI视频广告生成平台,自动生成可直接投放的视频。

下载
const twoSum = (nums, target) => {
  return nums.reduce((acc, ele, index) => {
    const complement = target - ele;
    // 若补数已存在,遍历其所有历史索引,生成索引对
    if (acc.map.has(complement)) {
      for (const compIndex of acc.map.get(complement)) {
        acc.result.push([compIndex, index]);
      }
    }
    // 将当前元素索引存入 map(支持重复值)
    if (!acc.map.has(ele)) acc.map.set(ele, []);
    acc.map.get(ele).push(index);
    return acc;
  }, { map: new Map(), result: [] }).result;
};

// 测试用例
console.log(twoSum([2, 7, 11, 15], 9));        // [[0, 1]]
console.log(twoSum([3, 2, 3], 6));            // [[0, 2]]
console.log(twoSum([2, 7, 11, 7, 15, 2, 7], 9)); 
// [[0,1], [0,3], [0,6], [1,5], [3,5], [5,6]]

⚠️ 注意事项:

  • 返回格式为二维数组 [[i, j]],明确区分索引对顺序(前小后大,按遍历顺序自然保证 i
  • 若只需任一解(如 LeetCode 标准题),可在找到首个匹配时提前 return,进一步优化常数性能;
  • 避免使用 indexOf 或 lastIndexOf 查找重复值——它们内部是 O(n) 线性扫描,会使整体退化为 O(n²);
  • 此解法不修改原数组,符合函数式编程原则,也便于测试与复用。

总结:处理非唯一元素的关键,在于放弃“值→单索引”的映射思维,升级为“值→索引集合”。这一转变既保持了线性时间效率,又完整覆盖了所有合法索引组合,是工业级代码中应对数据不确定性的典型范式。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
golang map内存释放
golang map内存释放

本专题整合了golang map内存相关教程,阅读专题下面的文章了解更多相关内容。

2025.09.05

750

5

golang map相关教程
golang map相关教程

本专题整合了golang map相关教程,阅读专题下面的文章了解更多详细内容。

2025.11.16

343

7

golang map原理
golang map原理

本专题整合了golang map相关内容,阅读专题下面的文章了解更多详细内容。

2025.11.17

553

20

java判断map相关教程
java判断map相关教程

本专题整合了java判断map相关教程,阅读专题下面的文章了解更多详细内容。

2025.11.27

323

6

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

100

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
誉天教育RHCE视频教程
誉天教育RHCE视频教程

共9课时 | 1.8万人学习

尚观Linux RHCE视频教程(二)
尚观Linux RHCE视频教程(二)

共34课时 | 7万人学习

尚观RHCE视频教程(一)
尚观RHCE视频教程(一)

共28课时 | 6万人学习