【算法】Split Array With Same Averag

题目

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input:
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.
Note:

The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].

数组 A 的长度为 1 ~ 30， A 中元素为大小为 0 ~ 10000 的整数，求 A 是否可以拆分为两个子数组 B 和 C，且 B 和 C 中元素加和的平均值相等。

解题思路

假设 A 可以拆分成符合条件的 B、C，A、B、C 的长度分别为 n、i、n-i ，则sumA/n == sumB/i == sumC/(n-i)。
由于所有元素均为整数，所以 sumA、sumB、sumC 均为整数，则 sumB == sumAi/n 为整数，则 sumAi%n == 0。
由于 1<=n<=30，1<=i<=n/2<=15，所以可以通过 sumA*i%n == 0 先寻找可能符合条件的 i 。
在找到 i 后，可以求出 sumB ，用 isExist 方法来判断 A 中是否存在 i 个元素加和为 sumB 的子数组。
isExist 方法中，通过 sumB 逐一减去元素，i-1，并进行递归，若最后 sumB 和 i 同时减为 0 ，说明有 i 个元素加和为 sumB，否则说明 i 不符合条件。

代码实现

Runtime: 16 ms
Memory: 20.8 MB

func splitArraySameAverage(_ nums: [Int]) -> Bool {
        // n 为 nums 的长度
        let n = nums.count
        // 长度为 0 或者 1 时，说明长度无法形成符合的分拆，返回 false
        if n < 2 { return false }
        // sum 为 nums 加和
        let sum = nums.reduce(0, +)
        // 循环 1 到 n/2
        for i in 1 ... n/2 {
            // 若存在 i 符合 (sum * i) % n == 0 则可能成功拆分成 i 和 n-i 个元素的符合的子数组
            if ((sum * i) % n == 0) {
                // 判断 nums 中从 nums[0] 开始，是否存在 i 个元素取得加和为 sum * i / n
                if isExist(nums, i, 0, sum * i / n) {
                    // 若可以 ，则符合条件，返回 true
                    return true
                }
            }
        }
        // 走到这里说明没有符合条件的 i ，返回 false
        return false
    }
    
    // 判断 nums 中从 nums[len] 开始，是否存在 idx 个元素取得加和为 sum
    func isExist(_ nums: [Int], _ len: Int, _ idx: Int, _ sum: Int) -> Bool {
        // 由于用的是加和值递减元素值得方法，所以当 sum 和 len 均为 0 时，说明是符合条件的，返回 true
        if sum == 0, len == 0 { return true }
        // idx len sum 非法时，返回 false
        if idx >= nums.count || len < 0 || sum < 0 { return false }
        // 从 idx 遍历到 end ，进行递归，用 sum-nums[i]，同事 len 长度 -1 ，i 起始索引 +1
        for i in idx..<nums.count {
            // 若 nums[i] == nums[i - 1] ，因为重复操作，可以跳过本次循环
            if i > idx && nums[i] == nums[i - 1] { continue }
            if isExist(nums, len - 1, i + 1, sum - nums[i]) { return true }
        }
        // 走到这里，没有遇到符合条件的 sum len，则返回 false
        return false
    }

代码地址：https://github.com/sinianshou/EGSwiftLearning