华为od 面试手撕真题【长度最小的子数组】

小咪咪 2023-09-27 20:30 15阅读 0赞

> 给定一个含有 n 个正整数的数组和一个正整数 target 。
> 
> 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 \[numsl, numsl+1, ..., numsr-1, numsr\] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
> 
> 示例 1：
> 
> 输入：target = 7, nums = \[2,3,1,2,4,3\]  
> 输出：2  
> 解释：子数组 \[4,3\] 是该条件下的长度最小的子数组。  
> 示例 2：
> 
> 输入：target = 4, nums = \[1,4,4\]  
> 输出：1  
> 示例 3：
> 
> 输入：target = 11, nums = \[1,1,1,1,1,1,1,1\]  
> 输出：0

这个题目是leetcode的原题：[209][]

注意，注意，注意。

>  **想不到最优解没关系，但是你一定要能写出暴力遍历的方法。**
> 
> 面试官一般就会在你写出暴力遍历的方法之后，问你时间复杂度是多少，提示你会不会超时？你就顺着面试官的想法逐个说明白就行，这里能够直接体现出你的**交流能力和理解能力**。当然，如果你一上来就是前缀和或者把前缀和写的比较快的话，面试官肯定还会问你有没有更优的解法，这里就要多加注意面试中的玄学了，**做题不要太快，以免让面试官觉得出的题正好撞你枪口上了，会出另外一道题或者让你给出最优的解法**。

这题的正解方法是前缀和。刷机试题多的话，应该对这个不陌生。最优解法是滑动窗口，比较难想到。leetcode上各路大神解法都很全，我就不复制粘贴了。

双重循环暴力：O(n^2)时间复杂度

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)时间复杂度

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]; 
            // 为了方便计算，令 size = n + 1 
            // sums[0] = 0 意味着前 0 个元素的前缀和为 0
            // sums[1] = A[0] 前 1 个元素的前缀和为 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;
        }
    }

滑动窗口：O(n)

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;
        }
    }

[209]: https://leetcode.cn/problems/minimum-size-subarray-sum/