C#LeetCode刷题之#643-子数组最大平均数 I（ Maximum Average Subarray I）

问题

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

输入: [1,12,-5,-6,50,3], k = 4

输出: 12.75

解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

注意:

1 <= k <= n <= 30,000。
所给数据范围 [-10,000，10,000]。

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Input: [1,12,-5,-6,50,3], k = 4

Output: 12.75

Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

示例

public class Program {

    public static void Main(string[] args) {
        int[] nums = null;

        nums = new int[] { 1, 12, -5, -6, 50, 3 };
        var res = FindMaxAverage(nums, 4);
        Console.WriteLine(res);

        res = FindMaxAverage2(nums, 4);
        Console.WriteLine(res);

        res = FindMaxAverage3(nums, 4);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static double FindMaxAverage(int[] nums, int k) {
        //暴力解法，此解法LeetCode超时未AC
        if(k == 0) return 0;
        double sum = 0, max_sum = int.MinValue;
        for(int i = 0; i < nums.Length && i + k <= nums.Length; i++) {
            sum = 0;
            for(int j = i; j < i + k; j++) {
                sum += nums[j];
            }
            max_sum = Math.Max(sum, max_sum);
        }
        return max_sum / k;
    }

    private static double FindMaxAverage2(int[] nums, int k) {
        //FindMaxAverage的优化解法，不必每次计算k个数字的和
        //把k当成一把尺子，从数组左边向右移动，尺子遮挡的部分看成和
        //只需用之前存的和减去数组左边移出尺子的值加上数组右边移入尺子的值即为新和
        if(k == 0) return 0;
        double sum = 0, max_sum = int.MinValue;
        //初始状态先计算前k个值的和
        for(int i = 0; i < k; i++) {
            sum += nums[i];
            max_sum = sum;
        }
        for(int i = 1; i < nums.Length && i + k <= nums.Length; i++) {
            //加右减左得到新和
            sum += nums[i + k - 1] - nums[i - 1];
            max_sum = Math.Max(sum, max_sum);
        }
        return max_sum / k;
    }

    private static double FindMaxAverage3(int[] nums, int k) {
        //一种常用的数组和的解决方案
        int n = nums.Length;
        //创建一个新的数组记录前面所有值的和，姑且称为“和数组”
        int[] sums = nums.Clone() as int[];
        //从第2个（索引为1）数字开始，记录之前所有值的和
        for(int i = 1; i < n; ++i) {
            sums[i] = sums[i - 1] + nums[i];
        }
        //定义最大值为前k个数，声明为double是为了最后可以直接返回结果而不用转换
        //C#或Java中，整数除以整数得到的结果还是整数，例如10 / 3 = 3，而不是 3.333333
        double max = sums[k - 1];
        //从k遍历“和数组”到最后，sums[i] - sums[i - k]为中间k个数字的和
        for(int i = k; i < n; ++i) {
            max = Math.Max(max, (double)sums[i] - sums[i - k]);
        }
        //返回最大平均数
        return max / k;
    }

}

以上给出3种算法实现，以下是这个案例的输出结果：

12.75
12.75
12.75

分析：

显而易见，FindMaxAverage的时间复杂度为：   ，FindMaxAverage2和FindMaxAverage3的时间复杂度为：  。