| 2024-04-05 |

# 长度最小的子数组

前言：这题也算是中等题目我次次做次次错，我自然是知道自己的坏习惯的每次隔个几个月就暗暗下定决心刷算法。然后每次都是从一开始写就感到挫折。一道题写半天还是错啊，一道题想一天还是没思路啊巴拉巴拉。不知不觉大部分业务都能写了，结果算法还是一窍不通。自感悲哀

# 题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的连续

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度 **。** 如果不存在符合条件的子数组，返回 0 。

示例 1：
1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
1
2
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：

1 <= target <= 109

1 <= nums.length <= 105

1 <= nums[i] <= 105

进阶：

如果你已经实现 O(n) 时间复杂度的解法，请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解法 1 暴力解法：

我的解答：

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int result = int.MaxValue;
        int i =0;
        for(i= 0;i<nums.Length;i++){
            int sum = 0;
            for(int j = i; j<nums.Length;j++){
                sum += nums[j];
                if(sum >= target){
                    if((j - i)+1 <= result)
                    result = (j - i)+1;
                }
            }
        }
        return result == int.MaxValue? 0 : result;
    }
}

因为力扣已经不让用这种方法去解答了会超时

但这样写应该是能符合需求的

标准答案 C++ 的暴力循环

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

答案的写法可读性和性能肯定比我的好

好了上面都是没啥用的因为这题要用滑动窗口去写

示例图：

209.长度最小的子数组

# 题解

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int i = 0; //滑动窗口起始位置
        int j = 0; //滑动窗口终止位置  这里注意 j是循环完一次数组的
        int subSize = 0; //窗口长度
        int result = int.MaxValue; //依旧是结果从最大值取起
        int sum = 0; //总和 这里注意不要放内部计算 在循环内部会加加减减
        for(j=0;j<nums.Length;j++){
            sum += nums[j];
            while(sum >= target){
                //计算窗口长度
                subSize = j-i+1;
                //判断一下结果与窗口长度 如果结果小于窗口 不赋值 为最大值 
                result = result < subSize? result :subSize;
                sum -= nums[i];
                //起始位置前移
                i++;
            }
        }

        return result == int.MaxValue? 0:result;
    }
}

这里说一个可笑的小插曲

我注意一下如果换成 result = result < subSize? result :subSize; 这句其实一样但我写题的时候纠结很久因为我当时纠结的地方错了我以外如果判断顺序反了比如写成 result = subSize< result ? subSize :result ; 我想 result 就不可能为 int.MaxValue 那如何有让 result 保持初始值的情况呢。其实是我忽略了 while 中的判断条件如果 while 根本不进入那 result 就会一直保持初始值。这里只是我想错了导致的无意义纠结。

tags: #算法