【萌新解题】三数之和
关于我:微信公众号:面试官问,原创高质量面试题,始于面试题,但不止于面试题。【萌新解题】系列文章试图从新人的角度去看待和解决力扣题目,本题是力扣第 15 题:[三数之和](https://leetcode.cn/problems/3sum/)。
题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
解题说明
本题要求找出整数数组中符合条件的三元组,使三元组中三个元素之和等于 0,而且不能包含重复元素,因此,我们可以先对数组进行排序,对于相同的元素,排序后是挨在一起的,类似 [1,1,2,2,2,3,3],这样我们可以很容易跳过重复元素,具体可以参考https://mp.weixin.qq.com/s/ZtEkRcQ2ujHYmUO3BlcXiw。
为了求出三元组,我们可以采用分而治之的思想,遍历数组,在每次循环中,先固定其中一个元素,然后在数组中剩下的元素中求出符合条件的二元组,那这个问题就退化为两数之和了,只不过在https://mp.weixin.qq.com/s/ZtEkRcQ2ujHYmUO3BlcXiw 这个题目中,结果返回的是符合条件的两个元素的下标,不是元素值,而且数组是从 0 开始查找,而在我们这个场景下,要求返回的是二元组(元素值),而且输入参数中,是从数组某个下标开始,不是固定的 0 开始,按照这个思路,我们可以写出代码的框架如下:
其中两数之和我们参考https://mp.weixin.qq.com/s/ZtEkRcQ2ujHYmUO3BlcXiw ,改造成如下形式即可:
版权声明: 本文为 InfoQ 作者【面试官问】的原创文章。
原文链接:【http://xie.infoq.cn/article/6164c9c509e478f524d7c0c4d】。文章转载请联系作者。
评论