【在 f****g 的大作中提到】 : Hey AprilFlower, why we could guarantee no duplicated elements by computing : s/N s%N, t/N and t%N? thanks a lot!
r*u
20 楼
我觉得你这算法的复杂度是O(n^3), inner loop是O(n),因为那俩pointer只需 走过input array一次。但out loop需要O(n^2)吧。 paul那个解法也是O(n^3)吧。第一步算完俩俩之和(call it Sum array)有O(n^2)个元 素,每个元素最多重复n次, 那给定一个元素x in Sum array,如果有另一个元素y in Sum array,x+y = 要求的数 ,x最多要比较n次。