LeetCode 209. Minimum Size Subarray Sum (O(n)实现)

分类：LeetCode动态规划

动态规划：

len[i]:

-若存在begin使得sum(nums.begin()+begin, nums.begin()+i+1)>=s且sum(nums.begin()+begin-1, nums.begin()+i+1)<s，那么len[i] = i – begin + 1 (这串数字的长度)

-反之，len[i] = len[i – 1] + 1;

sum[i]:

-若存在上述begin, sum =sum(nums.begin()+begin, nums.begin()+i+1)；

– 反之，sum = sum(nums.begin(), nums.begin()+i+1);

所求结果（函数返回值）即为：

min_element(len[i]); // 其中i满足sum[i] >= s

初始化：

len[0] = 1;

sum[0] = nums[0];

动态方程

参见代码中的for循环迭代。

时间复杂度分析

注意到，我们在循环外引入了一个变量begin. 时间复杂度分析与这个begin有关：

这有用到势能函数的概念，可以发现在整个函数中，，begin向前移进不会超过nums.size(), 这是我在嵌套for的判断条件中没有显式约定的。因此，这个嵌套for中的判断总共被执行的次数不会超过2n次，每次i都移进一次begin, 第二次判断时不满足约束，终止for. 所以其在函数中的复杂度为O(n).

而关于i的for循环，显然也是O(n).

所以函数的时间复杂度为O(n).

代码：

class Solution {public:int minSubArrayLen(int s, vector<int>& nums){if (nums.empty()){return 0;}vector<int> sum(nums.size(), 0);vector<int> len(nums.size(), 0);sum[0] = nums[0];len[0] = 1;int min_len = sum[0]>=s? 1: INT_MAX;int begin = 0;for (size_t i = 1; i < nums.size(); ++ i){sum[i] = sum[i-1] + nums[i];if (sum[i] < s){len[i] = len[i-1] + 1;} else{// note that this 'begin' won't be larger than nums.size()for (; sum[i] – nums[begin] >= s; sum[i] -= nums[begin], ++ begin) {}len[i] = i – begin + 1;min_len = min(min_len, len[i]);}}return min_len==INT_MAX? 0: min_len;}};

上一篇LeetCode 208. Implement Trie (Prefix Tree)下一篇LeetCode 210. Course Schedule II(拓扑排序-求有向图中是否存在环)

顶0踩0

人只要不失去方向，就不会失去自己

相关文章：

你感兴趣的文章：

标签云：