【附JS、Python、C++题解】Leetcode面试150题(9)——三数之和

devtools/2025/3/16 12:15:59/

一、题目​​​​​

15. 三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足:
i!=ji!=k 且 j!= k ,同时还满足:nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

二、思路

1. 我们要返回的是“所有和为0且不重复的三元组”,这是一个数组类型,数组里的每一个元素都是三元组;

2. 要有三个用于遍历的指针;

3. 判断条件就两个:

  • i!=ji!=k 且 j!= k 
  • nums[i] + nums[j] + nums[k] == 0、

4. 如果直接遍历,重复次数太多了,如何解决?

【联想到“两数之和Ⅱ”的那道题,因为有了一个“非严格递增”的顺序条件,我们得以简化遍历的过程;在这里也可以借鉴这个思路——创造一个顺序出来】

该题题解见如下文章:
【附JS、Python、C++题解】Leetcode面试150题(7)-CSDN博客

三、代码

① JavaScript

javascript">function threeNums(nums){nums.sort((a,b)->a-b);let res = [];let l = nums.length;for(let i = 0; i<l-2; i++){if(i>0 && nums[i]===nums[i-1]){continue;}let j = i+1;let k = l-1;while(j<k){const sum = nums[i] + nums[j] + nums[k];if(sum === 0){res.push([nums[i], nums[j], nums[k]]);while(j<k && nums[j] === nums[j+1]){j++;}while(j<k && nums[k] === nums[k-1]){k--;}j++;i--;}else if(sum<0){j++;}else{K--;}}}return res;
}

② Python

def three_sum(nums):nums.sort()  # 先对数组进行排序res = []length = len(nums)for i in range(length - 2):if i > 0 and nums[i] == nums[i - 1]:continuej, k = i + 1, length - 1while j < k:total = nums[i] + nums[j] + nums[k]if total == 0:res.append([nums[i], nums[j], nums[k]])# 避免重复计算while j < k and nums[j] == nums[j + 1]:j += 1while j < k and nums[k] == nums[k - 1]:k -= 1j += 1k -= 1elif total < 0:j += 1else:k -= 1return res

③ C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;int length = nums.size();// 先对数组进行排序sort(nums.begin(), nums.end());for (int i = 0; i < length - 2; ++i) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}int j = i + 1;int k = length - 1;while (j < k) {int total = nums[i] + nums[j] + nums[k];if (total == 0) {res.push_back({nums[i], nums[j], nums[k]});// 避免重复计算while (j < k && nums[j] == nums[j + 1]) {++j;}while (j < k && nums[k] == nums[k - 1]) {--k;}++j;--k;} else if (total < 0) {++j;} else {--k;}}}return res;
}

四、反思

这道题自己做的时候并没有先进行排序,导致重复的次数很多。下次遇到遍历很复杂的问题,要先进行处理!!


http://www.ppmy.cn/devtools/167548.html

相关文章

Java开发之数据库应用:记一次医疗系统数据库迁移引发的异常:从MySQL到PostgreSQL的“dual“表陷阱与突围之路

记一次医疗系统数据库迁移引发的异常&#xff1a;从MySQL到PostgreSQL的"dual"表陷阱与突围之路 一、惊魂时刻&#xff1a;数据库切换引发的系统雪崩 某医疗影像系统在进行国产化改造过程中&#xff0c;将原MySQL数据库迁移至PostgreSQL。迁移完成后&#xff0c;系…

Linux 文件与目录操作指令

以下是 Linux 文件与目录操作指令的详细整理&#xff0c;涵盖 基本操作、权限管理、查找统计、压缩解压 等场景&#xff0c;包含常用选项与示例&#xff1a; 一、目录导航与查看 1. pwd&#xff1a;显示当前目录的绝对路径 <BASH> pwd # 输出&#xff1a;/hom…

Vue 中的 MVVM、MVC 和 MVP 模式深度解析

文章目录 1. 模式概览与核心概念1.1 模式定义1.2 架构对比图 2. MVC 模式详解2.1 MVC 流程图2.2 Vue 中的 MVC 实现 3. MVP 模式详解3.1 MVP 流程图3.2 Vue 中的 MVP 实现 4. MVVM 模式详解4.1 MVVM 流程图4.2 Vue 中的 MVVM 实现 5. 模式对比分析5.1 职责对比5.2 通信方式对比…

Qt:槽函数与信号

1.槽函数的参数只能小于等于信号的参数&#xff0c;不然就报错 2.两者之间是多对多关系 3.可以使用信号触发信号间接的触发槽函数 4.断开信号与槽函数的连接 4.1断开一个信号与一个槽函数的连接 disconnect(this,SIGNAL(信号函数),this,SLOT(槽函数)); 4.2断开一个信号和…

Linux磁盘与存储管理:从“空间不足”到“存储大亨”

Linux磁盘与存储管理&#xff1a;从“空间不足”到“存储大亨” 引言 磁盘空间就像你的钱包&#xff0c;永远不够用。当你发现/home目录爆满时&#xff0c;那种焦虑感不亚于月底看到信用卡账单。但别担心&#xff0c;今天我们就来聊聊Linux磁盘与存储管理&#xff0c;让你从“…

如何在AVL树中高效插入并保持平衡:一步步掌握旋转与平衡因子 —— 旋转篇

文章目录 AVL树种旋转的规则右单旋右单旋代码左单旋左单旋代码左右双旋左右单旋的代码右左单旋右左单旋的代码 AVL树种旋转的规则 在AVL树中&#xff0c;旋转是为了保持树的平衡性。AVL树是一种自平衡的二叉搜索树&#xff0c;它要求每个节点的左右子树的高度差不能超过1。当插…

OpenFeign的配置类可以进行哪些配置

1. 日志级别&#xff08;Logger Level&#xff09; 工作原理 Feign的日志级别控制了日志输出的详细程度&#xff0c;有助于调试和监控。日志级别包括&#xff1a; NONE&#xff1a;不记录任何信息。BASIC&#xff1a;仅记录请求方法和URL及响应状态码和执行时间。HEADERS&am…

Excel表一键查询工具

Excel表格里面存放的数据文件太多&#xff0c;显得杂乱无章&#xff0c;无论是进行搜索还是定位特定数据&#xff0c;都变得异常繁琐且效率低下。为了改善这一状况&#xff0c;今天特意给大家推荐一款既轻便又实用的excel查询小工具&#xff0c;其软件包体积不到4M&#xff0c;…