Given an array S of n integers, are there elements abc in S such that a + b + c = 0?

Find all unique triplets in the array which gives the sum of zero.

题目大意:找到三个数的和为0.

Note: The solution set must not contain duplicate triplets.

 

原题链接:https://leetcode.com/problems/3sum/description/

 

就是找三个数的和为0的数组,不能有重复数组。

这道题是之前在58同城面试的时候碰到的。

当时的思路是排序,然后处理。

现在看来还是Too Young Too Simple…

这里首先是用到了Two Sum这道题的思想,将三个数的和为0 变化为 两个数的和为target。

然后还涉及一些去重优化。代码速度比较坑,最快到 102ms,慢的话到122ms…差不多了.

以上是代码。

接下来是参考链接:

http://blog.csdn.net/nanjunxiao/article/details/12524405

 

其他:

参考链接提到的Hash也想过,不过在3Sum下不太实用,就放弃了。

关于Set去重这个,我不太建议,个人尝试过,不太快,大概600ms左右…勉强通过的速度吧.

【LeetCode】15. 3Sum
Tagged on: