Thursday, December 20, 2018

[LeetCode]3Sum Smaller


这道题仍然是延续3Sum的解法,reduce成2Sum之后,双指针lo和hi,对于每一个lo,找到满足条件最大的hi,之后lo移去下一个位置。因为hi是单调递减的,所以这个过程O(N)可以完成,总的时间复杂度就是O(N^2),常数空间,代码如下:


No comments:

Post a Comment