突破点:如果到某个加油站剩余油量不足0,就从下一个加油站重新开始。
class Solution { public: /** * * @param gas int整型vector * @param cost int整型vector * @return int整型 */ int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { // write code here int size = gas.size(); int sum = 0, current = 0, idx = -1; for (int i = 0; i < size; ++i) { sum += gas[i] - cost[i]; current += gas[i] - cost[i]; if (current < 0) { current = 0; idx = i; } } return sum >= 0 ? idx + 1 : -1; } };