1664-生成平衡数组的方案数

Raphael Liu Lv10

给你一个整数数组 nums 。你需要选择 恰好 一个下标(下标从 0
开始)并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说,如果 nums = [6,1,7,4,1] ,那么:

  • 选择删除下标 1 ,剩下的数组为 nums = [6,7,4,1]
  • 选择删除下标 2 ,剩下的数组为 nums = [6,1,4,1]
  • 选择删除下标 4 ,剩下的数组为 nums = [6,1,7,4]

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等,该数组就是一个 平衡数组

请你返回删除操作后,剩下的数组 __nums __ 是 平衡数组方案数

示例 1:

**输入:** nums = [2,1,6,4]
**输出:** 1
**解释:**
删除下标 0 :[1,6,4] -> 偶数元素下标为:1 + 4 = 5 。奇数元素下标为:6 。不平衡。
删除下标 1 :[2,6,4] -> 偶数元素下标为:2 + 4 = 6 。奇数元素下标为:6 。平衡。
删除下标 2 :[2,1,4] -> 偶数元素下标为:2 + 4 = 6 。奇数元素下标为:1 。不平衡。
删除下标 3 :[2,1,6] -> 偶数元素下标为:2 + 6 = 8 。奇数元素下标为:1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。

示例 2:

**输入:** nums = [1,1,1]
**输出:** 3
**解释:** 你可以删除任意元素,剩余数组都是平衡数组。

示例 3:

**输入:** nums = [1,2,3]
**输出:** 0
**解释:** 不管删除哪个元素,剩下数组都不是平衡数组。

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

方法一:动态规划

思路与算法

首先题目给出一个下标从 0 开始长度为 n 的整数数组 nums,并给出「平衡数组」的定义:数组中奇数下标元素和与偶数下标元素的和相等。现在我们可以选择一个位置 i,0 \le i < n 的元素删除(注意删除后 i 之后的下标可能会因此发生改变)。我们需要求出所有删除该下标元素后的数组为「平衡数组」的下标数目。

我们设 preOdd}[i] 表示位置 i,0 \le i < n 前所有奇数位置元素的和,preEven}[i] 表示位置 i 前所有偶数位置元素的和,sufOdd}[i] 表示位置 i 后所有奇数位置元素的和,sufEven}[i] 表示位置 i 后所有偶数位置元素的和,我们来看如何进行状态转移——

  • 当 i 为奇数时:
    • preOdd}[i + 1] = \textit{preOdd}[i] + \textit{nums}[i],i + 1 < n
    • sufOdd}[i] = \textit{sufOdd}[i - 1] - \textit{nums}[i],i - 1 \ge 0
    • preEven}[i + 1] = \textit{preEven}[i],i + 1 < n
    • sufEven}[i] = \textit{sufEven}[i - 1],i - 1 \ge 0
  • 当 i 为偶数时:
    • preEven}[i + 1] = \textit{preEven}[i] + \textit{nums}[i],i + 1 < n
    • sufEven}[i] = \textit{sufEven}[i - 1] - \textit{nums}[i],i - 1 < n
    • preOdd}[i + 1] = \textit{preOdd}[i],i + 1 < n
    • sufOdd}[i] = \textit{sufOdd}[i - 1],i - 1 \ge 0

其中边界条件为:当 i = 0 时,preOdd}[0] = 0,preEven}[0] = 0,sufOdd}[0] = \sum_{2i + 1}^{n}\textit{nums}[2i + 1],sufEven}[0] = \sum_{2i}^{n}\textit{nums}[2i]。

不失一般性,现在我们将下标 i 的元素进行删除,显而易见下标 i 之前的元素下标并不会因此发生改变,而下标 i 之后的原本在 j,j > i 下标的数组元素会移动到下标 j - 1,即下标 i 之后的奇数下标元素会成为偶数下标元素,偶数下标元素会成为奇数下标元素。所以删除后数组中全部奇数下标元素和为 preOdd}[i] + \textit{sufEven}[i],全部偶数下标元素和为 preEven}[i] + \textit{sufOdd}[i],若两者相等则说明删除下标 i 后的数组为「平衡数组」。那么我们尝试删除每一个下标 i,0 \le i < n,来统计能生成「平衡数组」的下标即可。又因为 preOdd}[i],preEven}[i],sufOdd}[i],sufEven}[i] 求解都与前一个数有关,因此我们可以用「滚动数组」的技巧来进行空间优化。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def waysToMakeFair(self, nums: List[int]) -> int:
res = odd1 = even1 = odd2 = even2 = 0
for i, num in enumerate(nums):
if i & 1:
odd2 += num
else:
even2 += num
for i, num in enumerate(nums):
if i & 1:
odd2 -= num
else:
even2 -= num
if odd1 + even2 == odd2 + even1:
res += 1
if i & 1:
odd1 += num
else:
even1 += num
return res
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
int waysToMakeFair(vector<int>& nums) {
int odd1 = 0, even1 = 0;
int odd2 = 0, even2 = 0;
for (int i = 0; i < nums.size(); ++i) {
if (i & 1) {
odd2 += nums[i];
} else {
even2 += nums[i];
}
}
int res = 0;
for (int i = 0; i < nums.size(); ++i) {
if (i & 1) {
odd2 -= nums[i];
} else {
even2 -= nums[i];
}
if (odd1 + even2 == odd2 + even1) {
++res;
}
if (i & 1) {
odd1 += nums[i];
} else {
even1 += nums[i];
}
}
return res;
}
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int waysToMakeFair(int[] nums) {
int odd1 = 0, even1 = 0;
int odd2 = 0, even2 = 0;
for (int i = 0; i < nums.length; ++i) {
if ((i & 1) != 0) {
odd2 += nums[i];
} else {
even2 += nums[i];
}
}
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if ((i & 1) != 0) {
odd2 -= nums[i];
} else {
even2 -= nums[i];
}
if (odd1 + even2 == odd2 + even1) {
++res;
}
if ((i & 1) != 0) {
odd1 += nums[i];
} else {
even1 += nums[i];
}
}
return res;
}
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
public int WaysToMakeFair(int[] nums) {
int odd1 = 0, even1 = 0;
int odd2 = 0, even2 = 0;
for (int i = 0; i < nums.Length; ++i) {
if ((i & 1) != 0) {
odd2 += nums[i];
} else {
even2 += nums[i];
}
}
int res = 0;
for (int i = 0; i < nums.Length; ++i) {
if ((i & 1) != 0) {
odd2 -= nums[i];
} else {
even2 -= nums[i];
}
if (odd1 + even2 == odd2 + even1) {
++res;
}
if ((i & 1) != 0) {
odd1 += nums[i];
} else {
even1 += nums[i];
}
}
return res;
}
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int waysToMakeFair(int* nums, int numsSize) {
int odd1 = 0, even1 = 0;
int odd2 = 0, even2 = 0;
for (int i = 0; i < numsSize; ++i) {
if (i & 1) {
odd2 += nums[i];
} else {
even2 += nums[i];
}
}
int res = 0;
for (int i = 0; i < numsSize; ++i) {
if (i & 1) {
odd2 -= nums[i];
} else {
even2 -= nums[i];
}
if (odd1 + even2 == odd2 + even1) {
++res;
}
if (i & 1) {
odd1 += nums[i];
} else {
even1 += nums[i];
}
}
return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var waysToMakeFair = function(nums) {
let odd1 = 0, even1 = 0;
let odd2 = 0, even2 = 0;
for (let i = 0; i < nums.length; ++i) {
if ((i & 1) !== 0) {
odd2 += nums[i];
} else {
even2 += nums[i];
}
}
let res = 0;
for (let i = 0; i < nums.length; ++i) {
if ((i & 1) != 0) {
odd2 -= nums[i];
} else {
even2 -= nums[i];
}
if (odd1 + even2 === odd2 + even1) {
++res;
}
if ((i & 1) !== 0) {
odd1 += nums[i];
} else {
even1 += nums[i];
}
}
return res;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func waysToMakeFair(nums []int) (res int) {
var odd1, even1, odd2, even2 int
for i, num := range nums {
if i&1 > 0 {
odd2 += num
} else {
even2 += num
}
}
for i, num := range nums {
if i&1 > 0 {
odd2 -= num
} else {
even2 -= num
}
if odd1+even2 == odd2+even1 {
res++
}
if i&1 > 0 {
odd1 += num
} else {
even1 += num
}
}
return
}

复杂度分析

  • 时间复杂度:O(n),其中 n 为数组 nums 的长度。
  • 空间复杂度:O(1),仅使用常量空间。
 Comments
On this page
1664-生成平衡数组的方案数