added 643

pezy · pezy · commit ceb5757e7627 · 2018-12-09T23:46:55.000+08:00
diff --git a/643. Maximum Average Subarray I/README.md b/643. Maximum Average Subarray I/README.md
@@ -0,0 +1,26 @@
+这道题虽然是求平均数，但可以视为求和。且已经规定了连续数组，那么就完全可以想像成一个长度为 k 的滑块。从头滑到尾，统计一下最大那个和就好了。
+
+所以最常规的思路就是先求出滑块的初始和：
+
+```cpp
+double sum = 0.0;
+for (int i = 0; i != k; ++i) {
+  sum += nums[i];
+}
+```
+
+然后滑块开始滑动，滑动的过程可以理解为，去头接尾：
+
+```cpp
+for (int i = 1; i + k <= nums.size(); ++i) {
+  sum += nums[i+k-1] - nums[i-1];
+}
+```
+
+然后另设一个变量，如 max_sum 来统计最大的 sum 即可。
+
+----
+
+稍微 trick 一点的改进呢，就是把滑块想像成一个蠕虫。蠕虫拱起来的最高点就是它前进的标志。那么在这个问题里，我们最关心的就是求和这个过程，所以可以把这个最高点视为求和。
+
+那么蠕虫向前移动的步骤，就是不断累加和的过程，但吞一口，必须得拉一次，这个别忘了。
diff --git a/643. Maximum Average Subarray I/main.cc b/643. Maximum Average Subarray I/main.cc
@@ -0,0 +1,19 @@
+#include "solution.h"
+#define CATCH_CONFIG_MAIN
+#include "../Catch/single_include/catch.hpp"
+
+TEST_CASE("Test findMaxAverage", "[vector]") {
+  Solution s;
+  SECTION("example case") {
+    std::vector<int> arr{1, 12, -5, -6, 50, 3};
+    int k = 4;
+    double ans = s.findMaxAverage(arr, k);
+    REQUIRE(ans == 12.75);
+  }
+  SECTION("include zero") {
+    std::vector<int> arr{0, 4, 0, 3, 2};
+    int k = 1;
+    double ans = s.findMaxAverage(arr, k);
+    REQUIRE(ans == 4.0);
+  }
+}
diff --git a/643. Maximum Average Subarray I/solution.h b/643. Maximum Average Subarray I/solution.h
@@ -0,0 +1,18 @@
+#include <algorithm>
+#include <vector>
+using std::vector;
+
+class Solution {
+ public:
+  double findMaxAverage(vector<int>& nums, int k) {
+    for (int i = 1; i < k; ++i) {
+      nums[i] += nums[i - 1];
+    }
+    double sum = nums[k - 1];
+    for (int i = k; i < nums.size(); ++i) {
+      nums[i] += nums[i - 1];
+      sum = std::max<double>(sum, nums[i] - nums[i - k]);
+    }
+    return sum / k;
+  }
+};
