【Leetcode 每日一题】2270. 分割数组的方案数

问题背景

给你一个下标从 $0$ 开始长度为 $n$ 的整数数组 $nums$。
如果以下描述为真，那么 $nums$ 在下标 $i$ 处有一个 合法的分割：

• 前 $i+1$ 个元素的和 大于等于 剩下的 $n-i-1$ 个元素的和。
• 下标 $i$ 的右边 至少有一个 元素，也就是说下标 $i$ 满足 $0\le i<n-1$。

请你返回 $nums$ 中的 合法分割 方案数。

数据约束

● $1\le k\le nums.length\le 10^5$
● $-10^4\le nums[i]\le 10^4$

解题过程

要将数组分割成两部分，比较这两个部分和的关系，首先想到前缀和。
自己写的求了整个前缀和数组，需要同等大小的额外空间。实际上，前缀和完全可以作为一个参数在流程中计算并使用。

具体实现

前缀和数组

class Solution {public int waysToSplitArray(int[] nums) {int n = nums.length;long[] preSum = new long[n];preSum[0] = nums[0];for(int i = 1; i < n; i++) {preSum[i] = preSum[i - 1] + nums[i];}int res = 0;for(int i = 0; i < n - 1; i++) {if(preSum[i] >= preSum[n - 1] - preSum[i]) {res++;}}return res;}
}

流程中计算

class Solution {public int waysToSplitArray(int[] nums) {long total = 0;for(int num : nums) {total += num;}int res = 0;long sum = 0;for(int i = 0; i < nums.length - 1; i++) {sum += nums[i];// 这里将乘法转化为除法会出现舍入的问题，索性就用乘法if(2 * sum >= total) {res++;}}return res;}
}