You are given a 0-indexed integer array nums of length n. The number of ways to partition nums is the number of pivot indices that satisfy both conditions:


	1 &lt;= pivot &lt; n
	nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]


You are also given an integer k. You can choose to change the value of one element of nums to k, or to leave the array unchanged.

Return the maximum possible number of ways to partition nums to satisfy both conditions after changing at most one element.

&nbsp;
Example 1:

Input: nums = [2,-1,2], k = 3
Output: 1
Explanation: One optimal approach is to change nums[0] to k. The array becomes [3,-1,2].
There is one way to partition the array:
- For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.


Example 2:

Input: nums = [0,0,0], k = 1
Output: 2
Explanation: The optimal approach is to leave the array unchanged.
There are two ways to partition the array:
- For pivot = 1, we have the partition [0 | 0,0]: 0 == 0 + 0.
- For pivot = 2, we have the partition [0,0 | 0]: 0 + 0 == 0.


Example 3:

Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
Output: 4
Explanation: One optimal approach is to change nums[2] to k. The array becomes [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14].
There are four ways to partition the array.


&nbsp;
Constraints:


	n == nums.length
	2 &lt;= n &lt;= 105
	-105 &lt;= k, nums[i] &lt;= 105


class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int:
        prefix_sums = list(accumulate(nums))
        total_sum = prefix_sums[-1]
        best = 0
        if total_sum % 2 == 0:
            best = prefix_sums[:-1].count(total_sum // 2) # If no change

        after_counts = Counter(total_sum - 2 * prefix_sum
                               for prefix_sum in prefix_sums[:-1])
        before_counts = Counter()

        best = max(best, after_counts[k - nums[0]]) # If we change first num

        for prefix, x in zip(prefix_sums, nums[1:]):
            gap = total_sum - 2 * prefix
            after_counts[gap] -= 1
            before_counts[gap] += 1

            best = max(best, after_counts[k - x] + before_counts[x - k])

        return best
class Solution {
    //time - O(n), space - O(n)
    public int waysToPartition(int[] nums, int k) {
        int n = nums.length;

        int[] pref = new int[n];
        pref[0] = nums[0];
        Map<Integer, Integer> count = new HashMap<>(); //contribution of prefixes without changing
        count.put(pref[0], 1);

        for (int i = 1; i < n - 1; i++){
            pref[i] += pref[i - 1] + nums[i];
            count.put(pref[i], count.getOrDefault(pref[i], 0) + 1);
        }
        pref[n - 1] += pref[n - 2] + nums[n - 1]; //last step doesn't add into 'count' map, because we're trying to find at least two parts.

        int sum = pref[n - 1];
        int max = 0;
        if (sum % 2 == 0)
            max = count.getOrDefault(sum / 2, 0); //max without changing

        Map<Integer, Integer> countPrev = new HashMap<>(); //contribution of prefixes before current step
        for (int i = 0; i < n; i++){
            int diff = k - nums[i];
            int changedSum = sum + diff;
            if (changedSum % 2 == 0)
                max = Math.max(max, count.getOrDefault(changedSum / 2 - diff, 0) + countPrev.getOrDefault(changedSum / 2, 0));
            count.put(pref[i], count.getOrDefault(pref[i], 0) - 1);
            countPrev.put(pref[i], countPrev.getOrDefault(pref[i], 0) + 1);
        }
        return max;
    }
}
class Solution {
public:

    int waysToPartition(vector<int>& nums, int k) {
        unordered_map<long long int,int> left;
        unordered_map<long long int,int> right;

        long long int sum=accumulate(nums.begin(),nums.end(),0L);
        long long int leftSum=0;
        int n=nums.size();

        for(int i=0;i<n-1;i++){
            leftSum+=nums[i];
            long long int rightSum=sum-leftSum;
            long long int difference=leftSum-rightSum;
            right[difference]++; //storing difference count in right, since no difference exist in left
        }

        int res=right[0]; // Point Zero difference are the partition points
        leftSum=0;
        for(int i=0;i<n;i++){
            long long int D=k-nums[i];
            res=max(res,right[-D]+left[D]); // We can run a few test cases and see that if we replace arr[i] by k, the difference D, the left side including i,each element decreases by D while the right Side each element increases by D, so we find -D on right Side... WHY?? if right side is increasing by D, we need to find -D since this will result in -D+D=0, which are our partition points, since point 0 signifies a partition where leftSum==rightSum, similarly, left side decreases by D, so we find +D on left since this will result in zero as well.

            leftSum+=nums[i];
            long long int rightSum=sum-leftSum;
            left[leftSum-rightSum]++; //Now since we are moving our i forward, we are gonna change the next i point, so we are placing leftSum-RightSum on left side
            right[leftSum-rightSum]--; // From right we are gonna decrease it and transfer to left side
            if(right[leftSum-rightSum]==0){
                right.erase(leftSum-rightSum);
            }
        }
        return res;
    }
};
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var waysToPartition = function(nums, k) {
    let totalSum=nums.reduce((acc, curr) => acc+curr)
    let left=0;
    let rightDiff={}
    let leftDiff={}
    
    for(let i=0; i<nums.length-1; i++) {
        left+=nums[i]
        const right=totalSum-left
        if(rightDiff[left-right]) rightDiff[left-right]++
        else rightDiff[left-right]=1
    }

    let maxPartition=rightDiff[0] ? rightDiff[0] : 0
    left=0
    for(let i=0; i<nums.length; i++) {
        left+=nums[i]
        let diff=k-nums[i]
        const right=totalSum-left
        let leftVal=leftDiff[`${diff}`] ? leftDiff[`${diff}`] : 0
        let rightVal=rightDiff[`${-diff}`] ? rightDiff[`${-diff}`] : 0
        
        maxPartition=Math.max(maxPartition, leftVal+rightVal)
        if(leftDiff[left-right]) leftDiff[left-right]++
        else leftDiff[left-right]=1
        
        rightDiff[left-right]--

    }
    
    return maxPartition

};
```
Maximum Number of Ways to Partition an Array