arrays - 网格总和中其索引小于 K 的点数

Question

给定一个网格，如果机器人可以探索 X，Y（坐标）的数字总和小于 K 的点，则找出机器人可以导航的点数。

一个明显的解决方案是 O(n^2)。（遍历 2D 矩阵并根据条件接受/忽略一个点）其他是在数组中取 0 到 K-1 个元素，然后找到 2 个元素，使得总和为小于 K。涉及 O(k) 空间和 O(k) 时间。

任何人都可以提出一些更好的方法，在时空方面改进任何东西。我正在寻找更好的答案。

Answer 1

该等式在您的网格中x+y = K定义了一条对角线，从西北的一点到东南的一点。

如果网格中的点都是 和 的整数值，并且x也是整数，那么对角线 ( ) 以南的点数将为。yKx+y < KK(K-1)/2

包括对角线 ( ) 在内的网格中的点数x+y <= K将为K(K+1)/2。

显然，这是在恒定时间内计算的O(1)。