生成平衡数组的方案数【LC1664】

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

出去玩好累 不想出去玩了

预处理+枚举

• 思路：

  • 枚举每一个删除的位置，判断删除后奇数下标元素之和与偶数下标元素之和是否相等。假设删除的下标为iii，那么nums[0,i-1]范围内的奇偶性不变，nums[i+1,n-1]范围内的下标奇偶性倒置，奇数下标变为偶数下标，偶数下标变为奇数下标。由此可得：
    • 删除后奇数下标元素之和=nums[0,i-1]中奇数下标元素之和+nums[i+1,n-1]中偶数下标元素之和
    • 删除后偶数下标元素之和=nums[0,i-1]中偶数下标元素之和+nums[i+1,n-1]中奇数下标元素之和
  • 因此可以计算原数组的奇数下标元素和偶数下标元素的前缀和数组oddSum和evenSum，快速计算出某个范围内的奇数之和或者偶数之和
    • oddSum[i]代表前iii个奇数之和
    • evenSum[i]代表前iii个偶数之和

• 实现：两个前缀和数组

  class Solution {public int waysToMakeFair(int[] nums) {       int n = nums.length;if (n == 1) return 1;int[] oddSum = new int[n];int[] evenSum = new int[n];// 初始化前缀和数组evenSum[0] = nums[0];evenSum[1] = nums[0];oddSum[1] = nums[1];int count = 0;for (int i = 2; i < n; i++){if (i % 2 == 0){evenSum[i] = evenSum[i - 2] + nums[i];oddSum[i] = oddSum[i - 1];}else{oddSum[i] = oddSum[i - 2] + nums[i];evenSum[i] = evenSum[i - 1];}}// 枚举每个下标for (int i = 0; i < n; i++){int odd = i >= 1 ? oddSum[i - 1]  : 0;odd += evenSum[n - 1] - evenSum[i]; int even = i >= 1 ? evenSum[i - 1] : 0;even += oddSum[n - 1] - oddSum[i];                       if (even == odd){count++;}           }return count;}
  }
  

  • 复杂度分析

    • 时间复杂度：O(n)O(n)O(n)
    • 空间复杂度：O(n)O(n)O(n)

• 优化1：思路同上，枚举每个位置iii，仍是将和分为两个部分odd和even，使用int变量代替前缀和数组，优化空间复杂度。

  • 首先预处理得到原始数组的偶数下标元素之和s1s_1s1​和奇数下标之和s2s_2s2​，并记录当前枚举到的偶数下标之和t1t_1t1​以及奇数下标之和t2t_2t2​

  • 然后计算两个和，由于删除下标iii后，奇偶性倒置，因此根据iii进行处理

    odd=nums[0,i-1]中奇数下标元素之和+nums[i+1,n-1]中偶数下标元素之和

    even=nums[0,i-1]中偶数下标元素之和+nums[i+1,n-1]中奇数下标元素之和

    • 若iii为偶数
      even=t1+s2−t2odd=t2+s1−t1−nums[i]even = t_1+s_2-t_2\\ odd = t_2+s_1-t_1-nums[i] even=t1​+s2​−t2​odd=t2​+s1​−t1​−nums[i]

    • 若iii为奇数
      even=t1+s2−t2−nums[i]odd=t2+s1−t1even = t_1+s_2-t_2-nums[i]\\ odd = t_2+s_1-t_1 even=t1​+s2​−t2​−nums[i]odd=t2​+s1​−t1​

  class Solution {public int waysToMakeFair(int[] nums) {int s1 = 0, s2 = 0;int n = nums.length;for (int i = 0; i < n; ++i) {s1 += i % 2 == 0 ? nums[i] : 0;s2 += i % 2 == 1 ? nums[i] : 0;}int t1 = 0, t2 = 0;int ans = 0;for (int i = 0; i < n; ++i) {int v = nums[i];ans += i % 2 == 0 && t2 + s1 - t1 - v == t1 + s2 - t2 ? 1 : 0;ans += i % 2 == 1 && t2 + s1 - t1 == t1 + s2 - t2 - v ? 1 : 0;t1 += i % 2 == 0 ? v : 0;t2 += i % 2 == 1 ? v : 0;}return ans;}
  }作者：ylb
  链接：https://leetcode.cn/problems/ways-to-make-a-fair-array/solutions/2078792/by-lcbin-3jl3/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  

  • 复杂度分析

    • 时间复杂度：O(n)O(n)O(n)
    • 空间复杂度：O(1)O(1)O(1)

• 优化2：将优化1中的4个变量化简成一个变量s=odd1−even1−odd2+even2s=odd1-even1-odd2+even2s=odd1−even1−odd2+even2

  • 首先将所有偶数下标元素累加至s，将所有奇数下标累减至s
  • 然后枚举每个iii，当iii为奇数时累加，为偶数时减，当 s == 0 时答案加一

  把 odd1 + even2 == odd2 + even1 变形得 odd1 - even1 == odd2 - even2，这样可以化简成两个变量 s1 = odd1 - even1 和 s2 = odd2 - even2，如果 s1 == s2 答案就加一。s1 和 s2 的更新就是 i 为奇数加，为偶数减。

  再变形成 s1 - s2 == 0，那么令 s = s1 - s2，就可以化简成一个变量了，当 s == 0 时答案加一。

  class Solution {public int waysToMakeFair(int[] nums) {       int n = nums.length;int s = 0, count = 0;for (int i = 0; i < n; i++){s += i % 2 == 0 ? nums[i] : -nums[i];// 后}for (int i = 0; i < n; i++){s += i % 2 == 0 ? -nums[i] : nums[i];// 前+?if (s == 0) count++;s += i % 2 == 0 ? -nums[i] : nums[i];// 后+?}return count;}
  }
  

  • 复杂度分析

    • 时间复杂度：O(n)O(n)O(n)
    • 空间复杂度：O(1)O(1)O(1)