- Leetcode 3354. Make Array Elements Equal to Zero
- 1. 解题思路
- 2. 代码实现
- 题目链接:3354. Make Array Elements Equal to Zero
1. 解题思路
这一题是一道easy的题目,本来没想写的,因为完全可以暴力搞定,不过这里还是写了一下,因为这道题多少还是比较巧妙的,问题的描述一大把,事实上就是要分析在什么条件下可以使得数组归零,而这个的回答就是要求:
- 元素两侧的元素之和相同,此时往哪个方向开始均可以,有两种走法;
- 元素两侧的元素之差为1,此时往多的那一侧行走可以归零,有且只有一种走法;
因此,这道题事实上就变成一个累计数组的题目了, O ( N ) O(N) O(N)的算法复杂度即可完成。
2. 代码实现
给出python代码实现如下:
class Solution:def countValidSelections(self, nums: List[int]) -> int:s = sum(nums)pre = 0ans = 0for num in nums:left = preright = s-pre-numif num == 0:if left == right:ans += 2elif abs(left-right) == 1:ans += 1pre += numreturn ans
提交代码评测得到:耗时48ms,占用内存16.7MB。