Leetcode 3354 Make Array Elements Equal to Zero

题意：给定一个数组arr，有个cur使得nums[curr] == 0，一开始可以选择向左向右移动, 如果nums[cur] > 0, 那就 nums[cur] -= 1，并且移动的方向变更，求多少个cur的位置以及向左向右的方式能够使nums中的所有数字变化成0（想象一个球里面撞来撞去）

https://leetcode.com/problems/make-array-elements-equal-to-zero/description/

题解：本质上是找到一个每一个nums[cur] == 0的点，这个位置的左边所有数的和以及右边所有数的和相等或者相差1，如果是相等的话答案+2，如果相差1的话答案+1
由此想到前缀和

preS[i] == preS[n] - preS[i] 答案+2
preS[i] + 1 == preS[n] - preS[i] || preS[i] == preS[n] - preS[i] + 1 答案+1

class Solution {
public:
    int countValidSelections(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        vector<int> preS(n+1, 0);
        for(int i = 1; i < n+1; i++) {
            preS[i] = preS[i-1] + nums[i-1];
        }
        
        for(int i = 0; i < n; i++) {
            if(nums[i] == 0) {
                if(preS[i] == preS[n] - preS[i]) {
                    res += 2;
                } else if(preS[i] + 1 == preS[n] - preS[i] || preS[i] == preS[n] - preS[i] + 1) {
                    res += 1;
                }
            }
        }
        return res;
    }
};

时间复杂度$O(n)$
空间复杂度$O(n)$

原文地址：https://blog.csdn.net/xxxmmc/article/details/143855373

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！