题目
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
}
网友评论