209. 长度最小的子数组

链接

暴力法

未能通过全部测试用例。

C 代码:

// 计算子数组的和
int getSum(int start, int end, int* nums) {
    int sum = 0;
    while (start <= end) {
        sum += nums[start];
        start++;
    }
    return sum;
}

int minSubArrayLen(int target, int* nums, int numsSize) {
    int min = numsSize + 1; // 初始化最小子数组长度为数组长度加 1
    bool flag = false; // 定义一个布尔值表示是否找到了满足条件的子数组
    int i, j;
    for (i = 0; i < numsSize; i++) {                   // 遍历数组
        for (j = i, flag = false; j < numsSize; j++) { // 从当前元素开始往后找
            if (getSum(i, j, nums) >= target) {
                flag = true;
                break;
            }
        }
        // 如果确实找到了,那么判断是否需要更新最短值
        if (flag == true && j - i + 1 < min) {
            min = j - i + 1;
        }
    }
    if (min == numsSize + 1) {
        return 0;
    } else {
        return min;
    }
}

结果:超出时间限制, 18 / 21 个通过的测试用例

官方解答:

int minSubArrayLen(int s, int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }
    int ans = INT_MAX;
    for (int i = 0; i < numsSize; i++) {
        int sum = 0;
        for (int j = i; j < numsSize; j++) {
            sum += nums[j];
            if (sum >= s) {
                ans = fmin(ans, j - i + 1);
                break;
            }
        }
    }
    return ans == INT_MAX ? 0 : ans;
}

结果相同。包括通过测试用例的个数,也完全相同。

复杂度分析

时间复杂度: O ( n 2 ) O(n^2) O(n2),其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标,对于每个开始下标,需要遍历其后面的下标得到长度最小的子数组。

空间复杂度: O ( 1 ) O(1) O(1)

前缀和 + 二分查找

相关推荐

  1. 209.长度数组

    2024-06-10 06:12:01       32 阅读
  2. 209. 长度数组

    2024-06-10 06:12:01       42 阅读
  3. 209. 长度数组

    2024-06-10 06:12:01       4 阅读
  4. 力扣209-长度数组

    2024-06-10 06:12:01       33 阅读
  5. leetCode209.长度数组

    2024-06-10 06:12:01       15 阅读

最近更新

  1. svm 超参数

    2024-06-10 06:12:01       0 阅读
  2. shell判断语句练习

    2024-06-10 06:12:01       0 阅读
  3. MySQL周内训参照2、DDL与DML语句

    2024-06-10 06:12:01       0 阅读
  4. Scala学习笔记12: 高阶函数

    2024-06-10 06:12:01       0 阅读
  5. 详解 Flink CDC 的介绍和入门案例

    2024-06-10 06:12:01       0 阅读
  6. Nginx之Stream(TCP/UDP)负载均衡

    2024-06-10 06:12:01       0 阅读
  7. Sklearn简介、安装教程、入门学习

    2024-06-10 06:12:01       0 阅读

热门阅读

  1. 主从式光伏并网发电系统体系结构

    2024-06-10 06:12:01       5 阅读
  2. ICESat-2 ATL08 数据批量读取

    2024-06-10 06:12:01       5 阅读
  3. 发布自己的 npm 插件包:步骤与最佳实践

    2024-06-10 06:12:01       3 阅读
  4. spdlog源码解析

    2024-06-10 06:12:01       3 阅读
  5. Spring Boot集成thymeleaf快速入门demo

    2024-06-10 06:12:01       4 阅读
  6. 排查服务器cpu运行过高

    2024-06-10 06:12:01       4 阅读
  7. go语言切片去重的3种方式总结

    2024-06-10 06:12:01       3 阅读
  8. SpringMVC的执行流程

    2024-06-10 06:12:01       4 阅读
  9. mysql数据库安装_修改密码_忘记密码(修改)

    2024-06-10 06:12:01       3 阅读