Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

用个比较笨的方法来做,因为我本人目前并没有能力想到啥高深的算法来解决此问题。(废话)

首先计算数组内所有元素之和是否大于目标数,如果没有,则直接返回0。(感觉这里是可以优化的一个点)

设一个起始的标记start,从下标0开始,不断向右压缩找到最合适的起始点;同时初始化一个result=length

设游标cursor=start,sum=0;sum不断与cursor指向的元素相加并判断sum与目标数的大小,同时len(当前子数组的长度)自加,若sum>s,则把sum与len置零,更新cursor的位置,并且比较len与result的大小,若len<result,则更新result的值,重复执行此步骤

实现代码如下:

    public static int minSubArrayLen(int s, int[] nums) {
        int length = nums.length;
        if(length <= 0)
        {
            return 0;
        }
        int total = 0;
        for(int i = 0; i < length; i++)
        {
            total += nums[i];
        }
        if(total < s)
        {
            return 0;
        }
        int start = 0;
        int result = length;
        while(start < length)
        {
            int index = start;
            int cursor;
            int sum = 0;
            int len = 0;
            for(cursor = index; index < length; index++)
            {
                if(nums[cursor] >= s)
                {
                    return 1;
                }
                sum += nums[index];
                len++;
                if(sum >= s)
                {
                    if(len <= result)
                    {
                        result = len;
                    }
                    cursor = index;
                    sum = 0;
                    len = 0;
                    continue;
                }
            }
            start++;
        }
        return result;
    }
原文地址:https://www.cnblogs.com/WakingShaw/p/12076704.html