请问为什么我的代码会超时呢？

Question

public class Test {
    public int minSubArrayLen(int s, int[] nums) {
        int l=0;
        int r=-1;
        int res=nums.length+1;
        int sum=0;

        while(l<nums.length)
        {
            if(r+1<nums.length&&sum<s)
            {
                r++;
                sum+=nums[r];
            }else if(sum>=s)
            {
                l++;
                sum-=nums[l];
            }
            if(sum>=s)
                res=Math.min(res,r-l+1);
        }
        return res;

    }
    }

Answer 1

liuyubobobo 2019-04-03 13:24:27

你的算法不是超时，而是陷入了死循环。换句话说，l < nums.length 可能永远成立。

为你的程序添加这样的一个main函数就能测试出来。建议自己实际debug，看看为什么陷入了死循环？

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int l=0;
        int r=-1;
        int res=nums.length+1;
        int sum=0;
        while(l<nums.length)
        {
            if(r+1<nums.length&&sum<s)
            {
                r++;
                sum+=nums[r];
            }else if(sum>=s)
            {
                l++;
                sum-=nums[l];
            }
            if(sum>=s)
                res=Math.min(res,r-l+1);
        }
        return res;
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 2, 4, 3};
        int res = (new Solution()).minSubArrayLen(7, arr);
        System.out.println(res);
    }
}

==========

原因：

你的代码14行，只有在sum >= s的时候，才会l++，但是，如果既不满足这个if,又不满足else if，l就永远不会变，使得程序陷入死循环。

另外，这个else if里面的逻辑也有问题。应该先sum -= nums[l]，再l++。

课程代码的Java版本，可以参考：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/blob/master/03-Using-Array/Course%20Code%20(Java)/07-Minimum-Size-Subarray-Sum/src/Solution3.java

继续加油！：）

• 提问者 tataxqy #1

  老师你回复得好快！！！爱你！！

• 提问者 tataxqy #2

  可是老师，不是只有两种情况吗，大于s或者小于等于s

• liuyubobobo 回复 提问者 tataxqy #3

  你的else把 r+1<nums.length 也给刨除去了，所以没有包含 r+1 == nums.length 同时 sum < s的情况。实际跟踪一下看看，在你的各项数据都是什么的情况下，陷入了死循环？

点开查看后面1条评论