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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你一个整数数组 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-生成平衡数组的方案数