{"id":5057,"date":"2019-04-13T00:00:58","date_gmt":"2019-04-13T07:00:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5057"},"modified":"2019-04-13T00:06:02","modified_gmt":"2019-04-13T07:06:02","slug":"leetcode-209-minimum-size-subarray-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-209-minimum-size-subarray-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 209. Minimum Size Subarray Sum"},"content":{"rendered":"\n<p>Given an array of&nbsp;<strong>n<\/strong>&nbsp;positive integers and a positive integer&nbsp;<strong>s<\/strong>, find the minimal length of a&nbsp;<strong>contiguous<\/strong>subarray of which the sum \u2265&nbsp;<strong>s<\/strong>. If there isn&#8217;t one, return 0 instead.<\/p>\n\n\n\n<p><strong>Example:&nbsp;<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input:<\/strong> <code>s = 7, nums = [2,3,1,2,4,3]<\/code>\n<strong>Output:<\/strong> 2\n<strong>Explanation: <\/strong>the subarray <code>[4,3]<\/code> has the minimal length under the problem constraint.<\/pre>\n\n\n\n<p><strong>Follow up:<\/strong>If you have figured out the&nbsp;<em>O<\/em>(<em>n<\/em>) solution, try coding another solution of which the time complexity is&nbsp;<em>O<\/em>(<em>n<\/em>&nbsp;log&nbsp;<em>n<\/em>).&nbsp; <\/p>\n\n\n\n<p><strong>Solution 1: Two Pointers (Sliding Window)<\/strong><\/p>\n\n\n\n<p>Maintain a sliding window [l, r) such that sum(nums[l:r)) &gt;= s, then move l to l + 1, and move r accordingly to make the window valid.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int minSubArrayLen(int s, vector<int>& nums) {\n    int l = 0;\n    int r = 0;\n    int t = 0;\n    int ans = INT_MAX;\n    while (l < nums.size()) {\n      while (t < s &#038;&#038; r < nums.size()) t += nums[r++];      \n      if (t < s) break;\n      ans = min(ans, r - l);      \n      t -= nums[l++];\n    }\n    return ans == INT_MAX ? 0 : ans;      \n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an array of&nbsp;n&nbsp;positive integers and a positive integer&nbsp;s, find the minimal length of a&nbsp;contiguoussubarray of which the sum \u2265&nbsp;s. If there isn&#8217;t one, return&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[176],"tags":[215,41,175],"class_list":["post-5057","post","type-post","status-publish","format-standard","hentry","category-two-pointers","tag-sliding-window","tag-subarray","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5057","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5057"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5057\/revisions"}],"predecessor-version":[{"id":5059,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5057\/revisions\/5059"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5057"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5057"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5057"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}