Gas Station

https://leetcode.com/problems/gas-station/
题目解析，给定两个非负整形数组gas[] ，cost[], gas[i]代表到第i个点能加的油，cost[i]代表从第i个点走到下一个点要消耗的油（数组可循环走，即当i是数组最后一个元素是，下一个元素就是index为0的元素）。求：是否能找到一个index，让小车从index出发，顺时针绕数组走一周之后还能回到index
举例：
Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3
Input:
gas = [2,3,4]
cost = [3,4,3]

Output: -1

解题思路

• 从index 为0开始遍历，每次周游station一圈，看是否有满足条件的index
• 内部嵌套循环，起始位上一步的i，从当前i开始游走，每次走到index为j的地方，算上加油和耗油的数量，判断是否还有剩余remain

代码

        public int canCompleteCircuit(int[] gas, int[] cost) {
        int remain = 0;//油箱剩余的油
        int len = gas.length;

        //从第一个gas station开始计算，
        //判断从第i个gas station开始能否周游gas station
        for (int i = 0; i < len; i++) {
            remain = 0;
            int cnt = 0;
            //从当前station开始遍历
            //终止条件就是绕了一圈，所以每走一步cnt++，直到cnt ==len
            for (int j = i; cnt <= len; j = (j + 1) % len, cnt++) {
                remain += gas[j];
                remain -= cost[j];

                if (remain < 0) {
                    break;
                }
            }
            if(remain >=0){
                return i;
            }
        }

        return -1;
    }