給定一個(gè)含有?n?個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。

找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組?[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0 。

示例 1：

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組?[4,3]?是該條件下的長度最小的子數(shù)組。
示例 2：

輸入：target = 4, nums = [1,4,4]
輸出：1
示例 3：

輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0

這個(gè)題目是leetcode的原題：209

注意，注意，注意。

????????想不到最優(yōu)解沒關(guān)系，但是你一定要能寫出暴力遍歷的方法。

????????面試官一般就會(huì)在你寫出暴力遍歷的方法之后，問你時(shí)間復(fù)雜度是多少，提示你會(huì)不會(huì)超時(shí)？你就順著面試官的想法逐個(gè)說明白就行，這里能夠直接體現(xiàn)出你的交流能力和理解能力。當(dāng)然，如果你一上來就是前綴和或者把前綴和寫的比較快的話，面試官肯定還會(huì)問你有沒有更優(yōu)的解法，這里就要多加注意面試中的玄學(xué)了，做題不要太快，以免讓面試官覺得出的題正好撞你槍口上了，會(huì)出另外一道題或者讓你給出最優(yōu)的解法。

????????這題的正解方法是前綴和。刷機(jī)試題多的話，應(yīng)該對(duì)這個(gè)不陌生。最優(yōu)解法是滑動(dòng)窗口，比較難想到。leetcode上各路大神解法都很全，我就不復(fù)制粘貼了。

雙重循環(huán)暴力：O(n^2)時(shí)間復(fù)雜度

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= s) {
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

前綴和：O(nlogn)時(shí)間復(fù)雜度

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1]; 
        // 為了方便計(jì)算，令 size = n + 1 
        // sums[0] = 0 意味著前 0 個(gè)元素的前綴和為 0
        // sums[1] = A[0] 前 1 個(gè)元素的前綴和為 A[0]
        // 以此類推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

滑動(dòng)窗口：O(n)文章來源地址http://www.zghlxwxcb.cn/news/detail-624253.html

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

到了這里，關(guān)于華為od 面試手撕真題【長度最小的子數(shù)組】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！