美文网首页
3sum  closet

3sum  closet

作者: Deeglose | 来源:发表于2019-02-23 12:31 被阅读2次

    仍然使用2sum的方法,依次寻找最接近指定的数,并且仍然可以保证有方向地遍历。

    这依赖于一个很重要的性质:对于i,j圈定的范围,A[i]+A[j]仍然构成一个中间值,对于A[k0]+A[i]+A[j]  如果等于目标值 k0 i j就是解,否则,如果小于目标值,则可以证明解不可能在大于k0 i j的数值中产生,因此只能将j指针减小。同理,如果大于,需要将i指针增加。

    最终,在遍历的同时有方向性地选择。

    相关文章

      网友评论

          本文标题:3sum  closet

          本文链接:https://www.haomeiwen.com/subject/xnzuyqtx.html