LeetCode 题解工作台
设计相邻元素求和服务
给你一个 n x n 的二维数组 grid ，它包含范围 [0, n 2 - 1] 内的 不重复 元素。 实现 neighborSum 类： neighborSum(int [][]grid) 初始化对象。 int adjacentSum(int value) 返回在 grid 中与 value 相…
5
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以用一个哈希表 来存储每个元素的坐标，然后根据题意，分别计算相邻元素和对角线相邻元素的和。 时间复杂度方面，初始化哈希表的时间复杂度为 $O(m \times n)$，计算相邻元素和对角线相邻元素的和的时间复杂度为 。空间复杂度为 $O(m \times n)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个 n x n 的二维数组 grid，它包含范围 [0, n2 - 1] 内的不重复元素。
实现 neighborSum 类：
neighborSum(int [][]grid)初始化对象。int adjacentSum(int value)返回在grid中与value相邻的元素之和，相邻指的是与value在上、左、右或下的元素。int diagonalSum(int value)返回在grid中与value对角线相邻的元素之和，对角线相邻指的是与value在左上、右上、左下或右下的元素。
示例 1：
输入：
["neighborSum", "adjacentSum", "adjacentSum", "diagonalSum", "diagonalSum"]
[[[[0, 1, 2], [3, 4, 5], [6, 7, 8]]], [1], [4], [4], [8]]
输出： [null, 6, 16, 16, 4]
解释：
- 1 的相邻元素是 0、2 和 4。
- 4 的相邻元素是 1、3、5 和 7。
- 4 的对角线相邻元素是 0、2、6 和 8。
- 8 的对角线相邻元素是 4。
示例 2：
输入：
["neighborSum", "adjacentSum", "diagonalSum"]
[[[[1, 2, 0, 3], [4, 7, 15, 6], [8, 9, 10, 11], [12, 13, 14, 5]]], [15], [9]]
输出： [null, 23, 45]
解释：
- 15 的相邻元素是 0、10、7 和 6。
- 9 的对角线相邻元素是 4、12、14 和 15。
提示：
3 <= n == grid.length == grid[0].length <= 100 <= grid[i][j] <= n2 - 1- 所有
grid[i][j]值均不重复。 adjacentSum和diagonalSum中的value均在范围[0, n2 - 1]内。- 最多会调用
adjacentSum和diagonalSum总共2 * n2次。
解题思路
方法一：哈希表
我们可以用一个哈希表 来存储每个元素的坐标，然后根据题意，分别计算相邻元素和对角线相邻元素的和。
时间复杂度方面，初始化哈希表的时间复杂度为 ，计算相邻元素和对角线相邻元素的和的时间复杂度为 。空间复杂度为 。
class NeighborSum:
def __init__(self, grid: List[List[int]]):
self.grid = grid
self.d = {}
self.dirs = ((-1, 0, 1, 0, -1), (-1, 1, 1, -1, -1))
for i, row in enumerate(grid):
for j, x in enumerate(row):
self.d[x] = (i, j)
def adjacentSum(self, value: int) -> int:
return self.cal(value, 0)
def cal(self, value: int, k: int):
i, j = self.d[value]
s = 0
for a, b in pairwise(self.dirs[k]):
x, y = i + a, j + b
if 0 <= x < len(self.grid) and 0 <= y < len(self.grid[0]):
s += self.grid[x][y]
return s
def diagonalSum(self, value: int) -> int:
return self.cal(value, 1)
# Your NeighborSum object will be instantiated and called as such:
# obj = NeighborSum(grid)
# param_1 = obj.adjacentSum(value)
# param_2 = obj.diagonalSum(value)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on how the grid is scanned and how the sums are computed. An O(n²) scan is necessary to set up the grid, but after that, queries can be answered in constant time. Space complexity depends on the size of the precomputed hash map for storing the sums, which can also be O(n²). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Efficient use of hashing to reduce lookup time
- question_mark
Clear implementation of array scanning to locate elements
- question_mark
Accurate handling of edge cases in the grid, such as boundaries or missing neighbors
常见陷阱
外企场景- error
Incorrectly indexing out-of-bounds neighbors
- error
Inefficient re-scanning of the grid for each query
- error
Failure to handle grid boundaries properly, leading to errors when computing diagonal sums
进阶变体
外企场景- arrow_right_alt
Handling larger grids with more complex queries
- arrow_right_alt
Extending the problem to support dynamic grid updates
- arrow_right_alt
Optimizing for cases where grid size changes over time