网格总和中的索引数小于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).