使子数组元素和相等

You are given a 0-indexed integer array arr and an integer k. The array arr is circular. In other words, the first element of the array is the next element of the last element, and the last element of the array is the previous element of the first element.

You can do the following operation any number of times:

• Pick any element from arr and increase or decrease it by 1.

Return the minimum number of operations such that the sum of each subarray of length k is equal.

A subarray is a contiguous part of the array.

 

Example 1:

Input: arr = [1,4,1,3], k = 2
Output: 1
Explanation: we can do one operation on index 1 to make its value equal to 3.
The array after the operation is [1,3,1,3]
- Subarray starts at index 0 is [1, 3], and its sum is 4 
- Subarray starts at index 1 is [3, 1], and its sum is 4 
- Subarray starts at index 2 is [1, 3], and its sum is 4 
- Subarray starts at index 3 is [3, 1], and its sum is 4 

Example 2:

Input: arr = [2,5,5,7], k = 3
Output: 5
Explanation: we can do three operations on index 0 to make its value equal to 5 and two operations on index 3 to make its value equal to 5.
The array after the operations is [5,5,5,5]
- Subarray starts at index 0 is [5, 5, 5], and its sum is 15
- Subarray starts at index 1 is [5, 5, 5], and its sum is 15
- Subarray starts at index 2 is [5, 5, 5], and its sum is 15
- Subarray starts at index 3 is [5, 5, 5], and its sum is 15 

 

Constraints:

• 1 <= k <= arr.length <= 105
• 1 <= arr[i] <= 109

/*
题目思路：
1. 使用Stream计算每个位置的子数组总和。
2. 使用Stream计算目标总和。
3. 使用Stream计算总运算次数。
*/

import java.util.stream.IntStream;

public class Solution {
    public int minOperations(int[] arr, int k) {
        int n = arr.length;
        int[] subarraySum = new int[n];
        IntStream.range(0, n).forEach(i -> 
            IntStream.range(0, k).forEach(j -> 
                subarraySum[i] += arr[(i + j) % n]
            )
        );
        int totalSum = IntStream.of(subarraySum).sum();
        int targetSum = totalSum / n;
        int totalOperations = IntStream.of(subarraySum)
            .map(sum -> Math.abs(sum - targetSum))
            .sum();
        return totalOperations;
    }
}

此题解采用了基于余数分组的策略，考虑了循环数组的特性和子数组总和的均等性。具体方法是通过计算数组长度n与子数组长度k的最大公约数g，将原数组根据余数分为g组，每组的元素是从数组索引r开始，每隔g个元素取一个形成的子数组。由于要求每个长度为k的子数组的和相同，这实际上转化为了确保在所有循环中跨越数组的这些固定偏移集合中的元素总和相同。对每个分组计算将其中所有元素调整为中位数的代价，然后累计这些代价以得到最终答案。选择中位数是因为中位数是最小化绝对偏差之和的最优策略，这在统计学中是一个众所周知的事实。

O(n log(n/k))

O(n)