IOS 算法(中级篇) ----- 获取长度最小子数组

昨天做了个获取数组长度的题很有意思
如果你想知道什么题? 既然你诚心诚意的发问了, 我就大发慈悲的告诉你!

给定一个正整数的数组, 给定个正整数, 求正整数数组, 找出最小的连续数组使得相加之和>=给定的正整数, 没有返回0

例如 arr = [2, 3, 1, 2, 4, 3] , s = 7, 返回 [4, 3]

双循环
双循环, 暴力法是一个比较好理解的方法, 适合新手

1. 数组如果包含给定值 s, 直接弹出
2. 创建个初始的最小值
3. 第一层循环: 依次循环初始位 sum[i]
4. 第二层循环: i 之后的数字sum[j], 循环并相加, >= 给定值 s 时候判断 j-i+1 是否小于最小值min,
5. 如果小, min为 j-i+1, 否则 min还是之前值
6. 循环之后返回最小值

这里有几个点要注意一下
① 循环第二层j时, 如果找到>= s的时候,直接break, 减少不必要循环,
为什么呢? 因为再加已经没有意义, 我们找到的是 "长度最小的连续子数组", 而不是循环到底, 减少一定时间复杂度
② 留意初始设置的最小值min一定要"大"
③ 针对特殊情况, 数组包含s 特殊处理

swift

    func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
        // 如果数组包含s, 直接返回1, 包含最小长度即为1 
        if nums.contains(s) {
            return 1
        }
        // 设置初始值min, 最小值要大于数组长度, 我这里设置最小值为: 数组长度+1 
        // 小于的话会影响for下面判断, 不好处理
        // 等于的话要单独处理 数组之和全加完 >= s 情况
        var min = nums.count + 1

        // 开始循环数组
        for i in 0..<nums.count {
            // 设置初始和 sum 值为0
            var sum = 0
            for j in i..<nums.count {
                // 第二层循环, 依次累加
                sum = sum + nums[j]
                // 判断如果和大于等于s了, 弹出第二层循环, 再加也没有意义
                if(sum >= s){
                    //三目运算符 赋值min
                    min = (j-i+1)<min ? (j-i+1):min
                    break;
                }
            }
        }
        // 返回min, 如果min为初始值返回0
        return min==nums.count+1 ? 0:min;
    }

可看到, 这种方法节省空间复杂度, 但是在时间复杂度上却很耗, 由于双循环会使得时间复杂为O(n^2)
我更建议针对数据量小, 对内存消耗要求要低的情况下使用

双指针

双指针方法即: 定义两个指针, 循环开始位start, 循环结束位置end
循环判断 start位, end位 之间的元素和,
如果小于给定值s, end向右移动一位
如果大于给定值s, start向右移动一位,
依次判断 end - start + 1 与 min 的最小值赋给新的min, 最后返回最小 min

swift

    func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
        // 如果数组包含指定元素直接返回1
        if nums.contains(s) {
            return 1
        }
        // 定义初始值low high sum
        var low = 0, high = 0, sum = 0
        // 定义初始值min 大于数组长度即可
        var min = nums.count + 1
        // 循环high指针
        while high < nums.count  {
            // 总和加最新 nums[high]
            sum += nums[high]
            // 循环low指针
            while sum >= s  {
                // 取 min 和 high-low+1 的最小值 赋给新的 min
                min = (high-low+1)<min ? (high-low+1):min
                // 总和去掉之前的 nums[low]
                sum = sum - nums[low]
                // low向右移一位
                low += 1
            }
            // high向右移一位
            high += 1
        }
        // 三目运算符返回最小值
        return min==(nums.count + 1) ? 0:min;
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)

IOS 算法合集地址