用一堆bisect function可以过
但其实insort是O(N) 所以这样是O(N^2)
想当然是垫底
看答案
原来先sort+two pointer也行
我好笨
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
traveled = []
ans = 0
for num in nums:
idx_r = bisect_right(traveled, upper-num)
idx_l = bisect_left(traveled, lower-num)
ans += (idx_r-idx_l)
insort(traveled, num)
return ans