Meta VO 面试真题解析：连续子数组求和与二值网格最短路径

Given a sequence of integers and an integer total target, return whether a continuous sequence of integers sums up to target.

Example:

[1, 3, 1, 4, 23], 8: True (because 3 + 1 + 4 = 8)
[1, 3, 1, 4, 23], 7: False

You are given a game board represented as a 2D array of zeroes and ones. Zero stands for passable positions and one stands for impassable positions. Design an algorithm to find the shortest path from top left corner to bottom right corner.

For example, for the following board:

entrance -> 0 0 0 0 0 0 0
0 0 1 0 0 1 0
0 0 1 0 1 1 0
0 0 1 0 1 0 1
1 1 1 0 0 0 0 -> exit

A possible path is:

entrance -> + + + + 0 0 0
0 0 1 + 0 1 0
0 0 1 + 1 1 0
0 0 1 + 1 0 1
1 1 1 + + + + -> exit

Assuming a zero-indexed grid of rows and columns, with (0, 0) at the top left corner (entrance), we’d return the path coordinates from entrance to exit.

这类题包含两个常见面试变体：第一个是判断数组中是否存在一段连续子数组，使其和等于给定 target，通常可用前缀和配合哈希集合在线性时间内完成；第二个是二值网格最短路径问题，0 表示可通行、1 表示障碍，要求从左上角走到右下角并返回路径坐标，标准解法是 BFS，因为它能保证首次到达终点时路径最短。处理网格时通常需要记录访问状态和父节点，便于最后回溯出完整路径。