{"id":6306,"date":"2020-02-13T22:28:10","date_gmt":"2020-02-14T06:28:10","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6306"},"modified":"2020-02-13T22:33:02","modified_gmt":"2020-02-14T06:33:02","slug":"leetcode-1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sliding-window\/leetcode-1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold"},"content":{"rendered":"\n

Given an array of integers arr<\/code> and two integers k<\/code> and threshold<\/code>.<\/p>\n\n\n\n

Return the number of sub-arrays<\/em> of size k<\/code> and average greater than or equal to threshold<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4\nOutput:<\/strong> 3\nExplanation:<\/strong> Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [1,1,1,1,1], k = 1, threshold = 0\nOutput:<\/strong> 5\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5\nOutput:<\/strong> 6\nExplanation:<\/strong> The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [7,7,7,7,7,7,7], k = 7, threshold = 7\nOutput:<\/strong> 1\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [4,4,4,4], k = 4, threshold = 1\nOutput:<\/strong> 1\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= arr.length <= 10^5<\/code><\/li>
  • 1 <= arr[i] <= 10^4<\/code><\/li>
  • 1 <= k <= arr.length<\/code><\/li>
  • 0 <= threshold <= 10^4<\/code><\/li><\/ul>\n\n\n\n
    Solution: Sliding Window<\/strong><\/h2>\n\n\n\n
    1. Window size = k<\/li>
    2. Maintain the sum of the window<\/li>
    3. Check sum >= threshold * k<\/li><\/ol>\n\n\n\n
      Time complexity: O(n)
      Space complexity: O(1)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int numOfSubarrays(vector& arr, int k, int threshold) {\n    int ans = 0;\n    int sum = 0;\n    for (int i = 0; i < arr.size(); ++i) {\n      sum += arr[i];\n      if (i + 1 >= k) {\n        if (threshold * k <= sum) ++ans;\n        sum -= arr[i + 1 - k];\n      } \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      Given an array of integers arr and two integers k and threshold. Return the number of sub-arrays of size k and average greater than or equal to threshold. Example 1: Input: arr = [2,2,2,2,5,5,5,8], k…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[476],"tags":[327,177,215,41],"class_list":["post-6306","post","type-post","status-publish","format-standard","hentry","category-sliding-window","tag-k","tag-medium","tag-sliding-window","tag-subarray","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6306","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=6306"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6306\/revisions"}],"predecessor-version":[{"id":6308,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6306\/revisions\/6308"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6306"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6306"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6306"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}