公交最短距离-算法

题目

给定一个一维数组，其中每一个元素表示相邻公交站之间的距离，比如有四个公交站A,B,C,D，对应的距离数组为，1,2,3,4，如下图示

给定目标站X和Y，求他们之间最短的距离

解题

 遍历一次整个数组，将不再此区间内的和在此区间内的分别算一个综合，取其最小值

public class DistanceBetweenBusStopTest {

  public static void main(String[] args) {
    int[] distance = {1, 2, 3, 14};
    System.out.println(distanceBetweenBusStops(distance, 1, 4));
  }

  private static int distanceBetweenBusStops(int[] distance, int start, int destination) {
    int starti = Math.min(start, destination);
    int destinationi = Math.max(start, destination);

    int inLength = 0;
    int outLength = 0;
    for (int i = 0; i < distance.length; i++) {
      if (i + 1 >= starti && i + 1 < destinationi) {
        inLength += distance[i];
      } else {
        outLength += distance[i];
      }
    }
    return Math.min(inLength, outLength);
  }
}