一. 簡介

前面兩篇文章使用暴力解法，或者貪心算法解決了力扣網的加油站問題，文章如下：

力扣網編程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;    
}