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的整数值和 y , 和 K也是整数，则对角线以南的点数 ( x+y < K ) 将为 K(K-1)/2 .

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

显然，这是在常数时间内计算的 O(1) .