我该如何解决这个问题（leetcode式的技术问题）？
see*_*pig 2 python algorithm performance big-o list
假设给你一个整数对列表pairs和两个整数k1和k2。
从列表中查找满足以下条件的对的数量：
pairs[i][0] + pairs[j][0] <= k1pairs[i][1] + pairs[j][1] <= k2- 为了
i < j
例如，如果 、pairs=[[1,2],[2,3],[3,4],[4,5]]、k1=6和k2=7，结果应该是4，因为([1,2],[2,3])、([1,2],[3,4])、([1,2],[4,5])和([2,3],[3,4])都满足上述条件。
请参阅图片以更好地描述问题：
有没有一种方法可以比 O(n^2) 更高效地解决这个问题？到目前为止，这是我的解决方案：
pairs = [[1,2],[2,3],[3,4],[4,5]]
k1 = 6
k2 = 7
count = 0
n = len(pairs)
for i in range(n):
for j in range(i+1, n):
if pairs[i][0]+pairs[j][0] <= k1 and pairs[i][1]+pairs[j][1] <= k2:
count += 1
print(count)
这是 O(n log n)，并在大约 1.5 秒内解决最大允许输入 (n=2\xc3\x9710^5)：
\npairs = deque(sorted(pairs))\nys = SortedList(y for _, y in pairs)\ncount = 0\nwhile pairs:\n x, y = pairs[0]\n X, Y = pairs[-1]\n if x + X <= k1:\n ys.remove(y)\n count += ys.bisect_right(k2 - y)\n pairs.popleft()\n else:\n ys.remove(Y)\n pairs.pop()\n将这些对视为 (x,y) 对。按 x 坐标对它们进行排序，然后向内移动。令 (x,y) 为最左边的对，(X,Y) 为最右边的对。
\n- \n
如果 x+X \xe2\x89\xa4 k1，那么，关于 x 坐标，最左边的对可以与所有其他对组合（因为 X 是最大的）。但其中有多少也有一个合适的 y 坐标，即 y+y other \xe2\x89\xa4 k2 ？这意味着 y其他\xe2\x89\xa4 k2-y。为此，我们将所有 y 坐标保存在排序列表中。因为我们想要其他对，所以我们首先删除最左边的对自己的 y。然后我们对 k2-y 进行二分搜索，它告诉我们拟合其他对的数量。最后，我们将最左边的一对从进一步的考虑中删除，因为我们计算了它的所有贡献。
\n \n如果 x+X > k1，则最右边的对的 X 太大而无法与任何其他对组合。所以我们只需从 y 列表中删除它的 Y 并删除该对。
\n \n
我SortedList在那里用过。如果我们使用 Python list，该算法需要 O(n^2)，因为del需要线性时间。但由于常数因子非常小，所以对于最大允许输入仍然只需要大约 3 秒。
使用小示例和较大的随机输入测试结果：
\n4 pairs:\n count=4 0.000 s original\n count=4 0.000 s Kelly_SortedList\n count=4 0.000 s Kelly_list\n\n1000 pairs:\n count=51328 0.144 s original\n count=51328 0.003 s Kelly_SortedList\n count=51328 0.002 s Kelly_list\n\n6000 pairs:\n count=1845645 4.786 s original\n count=1845645 0.023 s Kelly_SortedList\n count=1845645 0.012 s Kelly_list\n\n200000 pairs:\n count=2022417695 1.490 s Kelly_SortedList\n count=2022417695 2.944 s Kelly_list\n\n400000 pairs:\n count=8075422313 3.454 s Kelly_SortedList\n count=8075422313 12.957 s Kelly_list\n代码：
\nfrom bisect import bisect_left, bisect_right\nfrom collections import deque\nfrom random import randrange\nfrom time import perf_counter as time\nfrom sortedcontainers import SortedList\n\n\ndef original(pairs, k1, k2):\n count = 0\n n = len(pairs)\n for i in range(n):\n for j in range(i+1, n):\n if pairs[i][0]+pairs[j][0] <= k1 and pairs[i][1]+pairs[j][1] <= k2:\n count += 1\n return count\n\n\ndef Kelly_SortedList(pairs, k1, k2):\n pairs = deque(sorted(pairs))\n ys = SortedList(y for _, y in pairs)\n count = 0\n while pairs:\n x, y = pairs[0]\n X, Y = pairs[-1]\n if x + X <= k1:\n ys.remove(y)\n count += ys.bisect_right(k2 - y)\n pairs.popleft()\n else:\n ys.remove(Y)\n pairs.pop()\n return count\n\n\ndef Kelly_list(pairs, k1, k2):\n pairs = deque(sorted(pairs))\n ys = sorted(y for _, y in pairs)\n count = 0\n while pairs:\n x, y = pairs[0]\n X, Y = pairs[-1]\n if x + X <= k1:\n del ys[bisect_left(ys, y)]\n count += bisect_right(ys, k2 - y)\n pairs.popleft()\n else:\n del ys[bisect_left(ys, Y)]\n pairs.pop()\n return count\n\n\nfuncs = original, Kelly_SortedList, Kelly_list\n\ndef test(funcs, *args):\n print(len(args[0]), \'pairs:\')\n for f in funcs:\n t0 = time()\n print(f\' count={f(*args)}\', f\'{time() - t0 :6.3f} s \', f.__name__)\n print()\n\ndef gen(n):\n pairs = [[randrange(2*10**5), randrange(2*10**5)] for _ in range(n)]\n k1 = 15 * 10**4\n k2 = 17 * 10**4\n return pairs, k1, k2\n\ntest(funcs, [[1,2],[2,3],[3,4],[4,5]], 6, 7)\ntest(funcs, *gen(1000))\ntest(funcs, *gen(6000))\ntest(funcs[1:], *gen(2*10**5))\ntest(funcs[1:], *gen(4*10**5))\n