仍然使用2sum的方法,依次寻找最接近指定的数,并且仍然可以保证有方向地遍历。
这依赖于一个很重要的性质:对于i,j圈定的范围,A[i]+A[j]仍然构成一个中间值,对于A[k0]+A[i]+A[j] 如果等于目标值 k0 i j就是解,否则,如果小于目标值,则可以证明解不可能在大于k0 i j的数值中产生,因此只能将j指针减小。同理,如果大于,需要将i指针增加。
最终,在遍历的同时有方向性地选择。
仍然使用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
网友评论