134. gas station

There is... On a ring road n A gas station , Among them the first i Gas stations have gas gas[i] l .

You have a car with unlimited tank capacity , From i A gas station goes to the i+1 A gas station needs gas cost[i] l . You start from one of the gas stations , The tank is empty at first .

Given two arrays of integers gas and cost , If you can drive around the loop , Then return to the number of the gas station at the time of departure , Otherwise return to -1 . If there is a solution , be Guarantee It is only Of .

Example 1:

Input : gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output : 3
explain :
from 3 Gas station ( The index for 3 It's about ) set out , Can be obtained 4 A litre of petrol . Now the tank has = 0 + 4 = 4 A litre of petrol
Go to 4 Gas station , Now the tank has 4 - 1 + 5 = 8 A litre of petrol
Go to 0 Gas station , Now the tank has 8 - 2 + 1 = 7 A litre of petrol
Go to 1 Gas station , Now the tank has 7 - 3 + 2 = 6 A litre of petrol
Go to 2 Gas station , Now the tank has 6 - 4 + 3 = 5 A litre of petrol
Go to 3 Gas station , You need to consume 5 A litre of petrol , Just enough for you to return to 3 Gas station .
therefore ,3 Can be the starting index .

Example 2:

Input : gas = [2,3,4], cost = [3,4,3]
Output : -1
explain :
You can't 0 Number or 1 Gas station No.1 starts , Because there's not enough gas to get you to the next gas station .
We from 2 Gas station No.1 starts , You can get 4 A litre of petrol . Now the tank has = 0 + 4 = 4 A litre of petrol
Go to 0 Gas station , Now the tank has 4 - 3 + 2 = 3 A litre of petrol
Go to 1 Gas station , Now the tank has 3 - 3 + 3 = 3 A litre of petrol
You can't go back 2 Gas station , Because the return journey costs 4 A litre of petrol , But your tank only has 3 A litre of petrol .
therefore , No matter what , You can't even drive around the loop .

Ideas

First create an array nums Save the difference between the amount of fuel this gas station can fill and the amount of fuel it consumes .

Simultaneous recording sum Look at the difference between the total fuel and the total mileage .

namely

 for (int i =0;i<nums.length;i++){
    
            nums[i] = gas[i] - cost[i];
            sum = nums[i]+sum;
        }

So if sum<0, It must be to return -1 Of

sum>0 There must be a solution , Specific coordinates need to be analyzed

sum>0:

utilize nums Array

gas = [1,2,3,4,5], cost = [3,4,5,1,2],nums=[-2,-2,-2,3,3]

We need to find one startIndex coordinate , You can start at this point and drive back to startIndex coordinate

We make use of temp Record the remaining fuel consumption per round

If you drive to the next gas station temp Not when it is negative ,

For a startIndex, Until you find one startIndex

if(sum>=0){
    
            int temp=0;
            int startIndex = 0;
            while (true){
    
                for (int i=startIndex;i<nums.length+startIndex;i++){
    
                    if(startIndex==nums.length-1) return startIndex;
                    int indexTemp = 0;
                    if(i<nums.length) indexTemp=i;
                    else indexTemp = i-nums.length;
                    temp = temp + nums[indexTemp];
                    if(temp<0){
    
                        temp=0;
                        startIndex = i+1;
                        break;
                    }
                    if(i==startIndex+nums.length-1&&temp>=0){
    
                        return startIndex;
                    }
                }

            }

        }

Complete code

class Solution {
    
    public int canCompleteCircuit(int[] gas, int[] cost) {
    
        int[] nums=new int[gas.length];
        int max = Integer.MIN_VALUE;
        int index = -1;
        int sum = 0;
        for (int i =0;i<nums.length;i++){
    
            nums[i] = gas[i] - cost[i];
            sum = nums[i]+sum;
        }
        if(sum>=0){
    
            int temp=0;
            int startIndex = 0;
            while (true){
    
                for (int i=startIndex;i<nums.length+startIndex;i++){
    
                    if(startIndex==nums.length-1) return startIndex;
                    int indexTemp = 0;
                    if(i<nums.length) indexTemp=i;
                    else indexTemp = i-nums.length;
                    temp = temp + nums[indexTemp];
                    if(temp<0){
    
                        temp=0;
                        startIndex = i+1;
                        break;
                    }
                    if(i==startIndex+nums.length-1&&temp>=0){
    
                        return startIndex;
                    }
                }

            }

        }
        else return -1;
    }
}