Leetcode 2607. Make K-Subarray Sums Equal

[Woodyiiiiiii]

这道题有两个卡点:

1. 循环数组如何对索引分类
2. 分类后如何求让子序列所有元素相等的最小花费

首先看到题目，解读题意，可以得出a1+a2+...ak=a2+a3+..ak+1，所以a1=ak+1。这样就转换了题意，可以对数组进行k个一组分类。

接着是第一个卡点，如何找到一个特定子序列的索引。我就是因为一直没发现之间的规律导致比赛中没想出来，不知道怎么解决循环数组这一难题。这里就引出个公式i=(i+k)%n，这样就能找到一个分组内所有的索引。循环数组一般都可以用%来解决这类问题。

第二个卡点有做过类似的题目，解决方法就是对数组排序，然后以中间数为标准，计算每个元素与其的绝对值。即使数组长度是偶数也没关系，取左边还是右边都是一样的。

class Solution {
    public long makeSubKSumEqual(int[] arr, int k) {
        int n = arr.length;
        long max = 0;
        for (int i = 0; i < arr.length; ++i) {
            List<Integer> list = new ArrayList<>();
            for (int j = i; arr[j] != 0; j = (j + k) % n) {
                list.add(arr[j]);
                arr[j] = 0;
            }
            Collections.sort(list);
            int mid = list.size() / 2;
            for (int j = 0; j < list.size(); ++j) {
                max += Math.abs(list.get(j) - list.get(mid));
            }
        }
        return max;
    }
}

---

• 462. Minimum Moves to Equal Array Elements II
• 2607. Make K-Subarray Sums Equal