当前位置：首页 > ops >正文

力扣网编程134题：加油站（双指针）

ops 2025/7/12 13:52:32

一. 简介

前面两篇文章使用暴力解法，或者贪心算法解决了力扣网的加油站问题，文章如下：

力扣网编程150题：加油站（暴力解法）-CSDN博客

力扣网编程150题：加油站（贪心解法）-CSDN博客

本文使用双指针解法来解决加油站题目。

二. 力扣网编程150题：加油站（中等）

解题思路三：（双指针）

使用双指针法求解的核心思路是：通过两个指针模拟"起点" 和 "终点" 的扩展，判断从起点能否到达终点并绕行一圈。

1. 总体判断：

如果总油量 total_gas < total_cost，则返回 -1（说明无论哪个起点出发都无法绕一圈）；

2. 双指针策略：

current_tank: 表示当前累计的油量（currtent += gas[i] + cost[i]）；

使用慢指针 start 模拟起点，使用快指针 fast模拟行驶；

如果 fast行驶到某个站时 current_tank < 0，说明从 start无法到达 fast站点，则将 start直接跳转到 fast+1（current_tank<0，说明在 start和 fast之间的任何一点都不能作为起点）；

3. 结果：循环结束，start 即为可绕一圈的起点。

答案在于总油量条件的保证：

当 total_tank >= 0 时，只要找到一个起点 start，使得从 start 到最后一个加油站的路径可行，那么从最后一个加油站绕回 start 的路径必然也可行（因为总油量足够）
因此，代码只需验证从 start 出发能否到达最后一个加油站即可，无需额外绕环。

C语言实现如下：

//双指针法（快慢指针）
//慢指针 start：模拟起点
//快指针 fast：模拟行驶路线
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {int i;int total_tank = 0;int start = 0; //尝试的起点int fast = 0;  //模拟的终点int current_tank = 0; //当前累积的油量//大体判断//如果总油量 < 总消耗，则说明无论哪个起点都无法绕一圈for(i = 0; i < gasSize; i++) {total_tank += gas[i]-cost[i];}if(total_tank < 0) {return -1;}//否则，必然存在一起出发可以绕一圈while(fast < gasSize) {current_tank += gas[fast]-cost[fast];//说明 从start无法到达 fast站点//那么在 start和 fast站之间的任何一点都不能作为起点if(current_tank < 0) {start = (fast+1) %gasSize;current_tank = 0;}fast++;}  return start;    
}