Leetcode209-Minimum Size Subarray Sum

新的個人部落格：Hu Haoyu’s Blog，歡迎參觀！

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

For example, given the array [2,3,1,2,4,3] and s = 7,

the subarray [4,3] has the minimal length under the problem constraint.

題意

給出一個包含n個正整數的數組和一個正整數s，找到長度最小的（連續）子數組使其和大于等于s。如果不存在這樣的子數組，傳回0。

比如數組為[2, 3, 1, 2, 4, 3]，s = 7。子數組[4, 3]是長度最小的子數組，其和4+3≥7。

分析

使用一種線上處理的方法，類似“數組的最大子數組和”的O(n)解法。

步驟

• 我們設定bottom和top控制子數組的頭部和尾部。
• 初始化bottom=0，top為-1，表示一個空的子數組。
• 子數組和sum=0，最小長度len=0。
• 當sum < s時，在目前子數組的尾部增加一個元素bottom[++top]。
• 當sum ≥ s時，去掉目前子數組的頭部元素，并++bottom。
• 退出循環的條件：top == nums.size() 或 bottom>top（此時已經存在最小len為1，不可能更小，可以退出）。

算法複雜度

由于top和bottom至多周遊一次數組nums，是以算法複雜度為O(n)。

更多練習

題目要求再給出一種O(nlogn)的解法。

簡略分析

采用分治法的思想。每次将區間A一分為二，成為A1和A2。子問題是求兩個子區間A1和A2中的各自的最小子數組長度len1和len2，以及區間A的最小子數組長度len中的最小值，即min{len1, len2, len}。

算法複雜度

由主定理（master定理）可知：T(n) = 2*T(n/2) + n，故算法複雜度為O(nlogn)。

AC代碼

O(n)及O(nlogn)算法

//O(n)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if (!nums.size()) return ;
        int bottom = , top = -;
        int sum = , len = ;
        while (true) {
            if (sum < s) {
                ++top;
                if (top != nums.size())
                    sum += nums[top];
                else
                    break;
            } else {
                sum -= nums[bottom]; ++bottom;
                if (bottom > top)
                    break;
            }
            if (sum >= s) {
                int new_len = top - bottom + ;
                if (!len || len && new_len < len)
                    len = new_len;
            }
        }
        return len;
    }
};

//O(nlogn)
class Solution {
public:
    int MAX_INT = ;
    int minSubArrayLen(int s, vector<int>& nums) {
        if (!nums.size()) return ;
        return findMinLen(s, nums, , nums.size() - );
    }
    int findMinLen(int s, vector<int>& nums, int bottom, int top) {
        if (top == bottom) return nums[top] >= s ?  : ;
        int mid = (bottom + top) / ;
        int left = mid, right = mid + , sum = , len;
        while (sum < s && (right <= top || left >= bottom)) {
            if  (right > top) {
                sum += nums[left]; --left;
            }
            else if (left < bottom) {
                sum += nums[right]; ++right;
            }
            else if (nums[left] > nums[right]) {
                sum += nums[left]; --left;
            }
            else {
                sum += nums[right]; ++right;
            }
        }
        if (sum >= s) {
            len = right - left - ;
            int leftLen = findMinLen(s, nums, bottom, mid);
            int rightLen = findMinLen(s, nums, mid + , top);
            return minValue(leftLen, rightLen, len);
        }
        else {
            return ;
        }
    }
    int minValue(int x, int y, int z) {
        if (!x) x = MAX_INT;
        if (!y) y = MAX_INT;
        if (x <= y && x <= z) return x;
        if (y <= x && y <= z) return y;
        return z;
    }
};
           

如分析或代碼有誤，請批評指正，謝謝。