leetcode 15–3sum

对于排序后的数组应充分利用顺序的性质,例如这一题需要在一个数组中找到和为0的三个数。因为是求和问题,首先排序可以方便查找。

在排好序后,由于需要找到三个数,首先确定最前面的也就是最小的数,写入for循环,后面的两个数需要通过双指针的方式就行一前一后的查找,结果大于0则后面的指针前移,小于0则前面的指针后移。

这种方法要快于用多层for循环,也算是充分利用了有序的性质。

由于题目要求找到所有的组合且不能有重复,所以在查找过程中每个位置遇到相同的数字,需要跳过。这样做不仅加快了执行速度,省去重复的时间,还保证了不会添加重复的组合。

最后的话,以后遇到排好序的数组,首先需要想到双指针法与折半查找法等,充分利用有序的性质。

Leave a Reply

Your email address will not be published. Required fields are marked *