#209 长度最小的子数组

题目

思路

这个题拿到之后首先考虑了两种思路。

第一种思路：从前往后遍历数组每一个数，从该数开始往后一直加，直到和大于等于target，就记录下该子串的长度，如果小于之前其他子串的长度，就用这个长度覆盖掉最小子数组长度，然后记录下该下标Index。这样的做法需要遍历每一个数，且最坏情况下，每一次都需要遍历到最后一个数才有结果，所以时间复杂度。

第二种思路，既然题目是要找最小长度的子串长度，那就让子串长度从0出发，去验证是否存在这样长度的子串。由于是从小到大进行判断，那么一旦检测到存在该长度的子串，那就可以直接结束循环了，此时已经找到题目要求的数组和长度了。虽然相较于第一种思路而言得到了优化，但是算法的时间复杂度仍然是。

代码

class Solution {

public:

    int minSubArrayLen(int target, vector<int>& nums) {

        int time,i,j,count=0;

        int sum[nums.size()];

        sum[0]=nums[0];

        for (i=1 ; i<nums.size();i++)

        {

          sum[i]=sum[i-1]+nums[i];     

        }

        for (time=1; time<nums.size()+1; time++)

        {

            for (i=0 ; i<(nums.size()-time+1); i++)

            {

                if (i==0)

                {

                    count=sum[time+i-1];

                }

                else {

                    count=sum[time+i-1]-sum[i-1];

                }       

                if (count>=target)

                {

                    return time;

                }

                count=0;

            }

        }

        return 0;

    }

};

反思

用的暴力版滑动窗口，结果非常丑陋，原先没优化的时候时间复杂度是，过不了最后两组数据量特别大的样例。我发现同一个窗口内有大量重复计算， 比如窗口大小为2的时候 要算num[0]+num[1]， 到窗口大小为3的时候 要算num[0]+num[1]+num[2]， 实际上这个num[0]+num[1]就一直在重复算。后来我先开了一个新数组sum，用来记录每个元素到第一个元素之间所有值的和sum[i]，这样num[1]+num[2]就可以表示为sum[3]-sum[0],num[2]+num[3]+num[4]=sum[4]-sum[1]，这个地方就优化为了。（不过还是好垃圾啊）

当然可以用双指针来做，我的思路是延续上面的sum数组，设置头尾两个指针，只要两者之间的差值大于target，就决定移动指针。如果头部指针+1带来的差值变化更小，就动头部指针。反之如果尾部指针-1带来的差值更小，就动尾部指针。直到两个指针之间距离小于等于target，那就找到了最小子串。（出了BUG 还在调试）