环形问题一般指有两个解，返回的最终答案却是二者之最优。常见的有：

• 时钟的夹角
• 公交站间的距离

一般的解题思路都差不多，从这些点出发准没有错：

• 首先求出总长度 sum。
• 然后后求出直观解 sub。
• 最后通过比较 sum - sub 与 sub 的优劣选取答案。

...
int sum = ?
int sub = ?
return chioce(sub-sub, sub);
...

C_01 时钟的夹角

方法一：互补法

复杂度分析

• 时间复杂度：$O()$O()，
• 空间复杂度：$O()$O()，

---

C_02 公交站间的距离

环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。

环线上的公交车都可以按顺时针和逆时针的方向行驶。

返回乘客从出发点 start 到目的地 destination 之间的最短距离。

输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。

方法一：互补法

本质和求时钟的夹角是一类题型。因为实在一个环形区域里面求最短路径，所以，我们应该要稍微「投机取巧」一下，

• 我们先求总长度 sum，然后求出 s 到 d 的距离 dis。
• 最后比较 dis 与 sum-dis 的大小即可。

public int distanceBetweenBusStops(int[] distance, int start, int destination) {
  int s = Math.min(start, destination);
  int d = Math.max(start, destination);
  
  int sum = 0;
  for (int dis : distance)     
  	sum += dis;

  int dis = 0;
  for (int i = s; i < d; i++)  
  	dis += distance[i];
  
  return Math.min(sum-dis, dis);
}

复杂度分析

• 时间复杂度：$O(n)$O(n)，
• 空间复杂度：$O(1)$O(1)，

---

A_04

方法一：

复杂度分析

• 时间复杂度：$O()$O()，
• 空间复杂度：$O()$O()，

---