题目

给你一个下标从 0 开始的整数数组 nums ，它包含 3 * n 个元素。

你可以从 nums 中删除 恰好 n 个元素，剩下的 2 * n 个元素将会被分成两个 相同大小 的部分。

• 前面 n 个元素属于第一部分，它们的和记为 sumfirst 。
• 后面 n 个元素属于第二部分，它们的和记为 sumsecond 。

两部分和的 差值 记为 sumfirst - sumsecond 。

• 比方说，sumfirst = 3 且 sumsecond = 2 ，它们的差值为 1 。
• 再比方，sumfirst = 2 且 sumsecond = 3 ，它们的差值为 -1 。

请你返回删除 n 个元素之后，剩下两部分和的 差值的最小值 是多少。

提示：

• nums.length == 3 * n
• 1 <= n <= 105
• 1 <= nums[i] <= 105

解题思路

目标是最小化 sumfirst - sumsecond。

1. 数组构成: 原始数组 nums 有 3n 个元素。我们要删除 n 个，剩下 2n 个。
2. 两部分划分: 剩下的 2n 个元素，按它们在原数组中的相对顺序排列，前 n 个构成第一部分，后 n 个构成第二部分。
3. 目标: 为了让 sumfirst - sumsecond 尽可能小，我们应该让 sumfirst 尽可能小，同时让 sumsecond 尽可能大。

我们可以设想一个“分割点” i，这个点将原数组 nums 分为两部分：

• 一个前缀 nums[0...i-1]
• 一个后缀 nums[i...3n-1]

第一部分的 n 个元素将完全从前缀中选出。 第二部分的 n 个元素将完全从后缀中选出。

思考一下分割点 i 的取值范围：

• 前缀 nums[0...i-1] 的长度至少要是 n，我们才能从中选出 n 个数。所以 i >= n。
• 后缀 nums[i...3n-1] 的长度也至少要是 n。后缀的长度是 3n - i，所以 3n - i >= n，即 i <= 2n。

所以，我们可以枚举所有可能的分割点 i，其中 n <= i <= 2n。

对于每一个固定的分割点 i：

1. 选择第一部分: 我们需要从前缀 nums[0...i-1] 中选出 n 个元素。为了让 sumfirst 最小，我们应该选择这 i 个数中最小的 n 个。
2. 选择第二部分: 我们需要从后缀 nums[i...3n-1] 中选出 n 个元素。为了让 sumsecond 最大，我们应该选择这 3n - i 个数中最大的 n 个。

然后，我们计算 sumfirst - sumsecond，并在所有可能的 i 中找到这个差值的最小值。

思路优化

最一般的思路，使用 sort 函数，直接在循环中对每个前缀和后缀进行排序来找最小/最大的 n 个数，从第 n 个到 2n 个数，外部循环是 n 次，内部使用排序的平均时间复杂度是 nlogn ，时间复杂度会是 O(n * nlogn) ，在本题的情况下不够快。

我们需要创建两个辅助数组，保存这n个情况下的两个部分的最大和最小值，并且需要在一次循环中完成，并且时间复杂度不能超过 O(logn)。对于这两个数组的计算最好的方法是使用优先队列（堆）。使用空间把要求的最大和最小值先保存下来，然后在 n 次循环中直接调用即可。

创建两个辅助数组：

1. prefix_min_sum[i]: 存储 nums[0...i] 中，最小的 n 个元素之和。
2. suffix_max_sum[i]: 存储 nums[i...3n-1] 中，最大的 n 个元素之和。

具体思路

步骤 1: 计算所有可能的前缀最小和 (prefix_min_sum)

• 我们从左到右遍历数组 nums。
• 使用一个大顶堆 (Max Heap)，大小保持为 n。这个堆里始终存放着我们到目前为止遇到的、构成最小和的 n 个数。堆顶就是这 n 个数里最大的那个。
• 具体操作:
  1. 初始化一个大顶堆 pq_max 和一个变量 current_sum = 0。
  2. 遍历 i from 0 to 3n-1：
  3. 将 nums[i] 加入 current_sum 并推入 pq_max。
  4. 如果 pq_max 的大小超过 n，说明我们加入了一个新数，需要踢掉一个最大的数来维持“最小和”。于是，将堆顶元素从 current_sum 中减去，并弹出堆顶。
  5. 当 pq_max 的大小正好为 n 时 (即 i >= n-1)，此时的 current_sum 就是 nums[0...i] 中最小的 n 个数之和。我们将其存入 prefix_min_sum[i]。

步骤 2: 计算所有可能的后缀最大和 (suffix_max_sum)

• 过程和步骤 1 类似，只是方向相反，目标也相反。
• 我们从右到左遍历数组 nums。
• 使用一个小顶堆 (Min Heap)，大小保持为 n。这个堆里始终存放着我们到目前为止遇到的、构成最大和的 n 个数。堆顶就是这 n 个数里最小的那个。
• 具体操作:
  1. 初始化一个小顶堆 pq_min 和一个变量 current_sum = 0。
  2. 逆序遍历 i from 3n-1 down to 0：
  3. 将 nums[i] 加入 current_sum 并推入 pq_min。
  4. 如果 pq_min 的大小超过 n，说明我们加入了一个新数，需要踢掉一个最小的数来维持“最大和”。于是，将堆顶元素从 current_sum 中减去，并弹出堆顶。
  5. 当 pq_min 的大小正好为 n 时 (即 i <= 2n)，此时的 current_sum 就是 nums[i...3n-1] 中最大的 n 个数之和。我们将其存入 suffix_max_sum[i]。

步骤 3: 合并结果，找到最终答案

• 使用 prefix_min_sum 和 suffix_max_sum 这两个预处理好的数组。
• 我们遍历所有可能的分割点 i，从 n 到 2n。
• 对于每个 i，第一部分是从 nums[0...i-1] 中选，第二部分是从 nums[i...3n-1] 中选。
  • sumfirst 就是 prefix_min_sum[i-1]。
  • sumsecond 就是 suffix_max_sum[i]。
• 计算差值 prefix_min_sum[i-1] - suffix_max_sum[i]。
• 在所有这些差值中找到最小值，即为最终答案。

代码实现

#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>

class Solution {
public:
    long long minimumDifference(std::vector<int>& nums) {
        int total_size = nums.size();
        int n = total_size / 3;

        // 辅助数组，prefix_min_sums[i] 表示 nums[0...i] 中 n 个最小元素的和
        std::vector<long long> prefix_min_sums(total_size, -1);
        // 这里把不使用的数全部填成-1
        
        // --- 步骤 1: 从左到右计算前缀的最小和 ---
        // 使用大顶堆来维护 n 个最小的元素
        std::priority_queue<int> pq_max;
        long long current_sum = 0;

        for (int i = 0; i < total_size; ++i) {
            current_sum += nums[i];
            pq_max.push(nums[i]);

            // 如果堆的大小超过 n，移除最大的元素以保持和最小
            if (pq_max.size() > n) {
                current_sum -= pq_max.top();
                pq_max.pop();
            }

            // 当堆的大小达到 n 时，记录当前的和
            if (pq_max.size() == n) {
                prefix_min_sums[i] = current_sum;
            }
        }

        // 辅助数组，suffix_max_sums[i] 表示 nums[i...3n-1] 中 n 个最大元素的和
        std::vector<long long> suffix_max_sums(total_size, -1);
        
        // --- 步骤 2: 从右到左计算后缀的最大和 ---
        // 使用小顶堆来维护 n 个最大的元素
        std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;
        current_sum = 0;

        for (int i = total_size - 1; i >= 0; --i) {
            current_sum += nums[i];
            pq_min.push(nums[i]);

            // 如果堆的大小超过 n，移除最小的元素以保持和最大
            if (pq_min.size() > n) {
                current_sum -= pq_min.top();
                pq_min.pop();
            }
            
            // 当堆的大小达到 n 时，记录当前的和
            if (pq_min.size() == n) {
                suffix_max_sums[i] = current_sum;
            }
        }

        // --- 步骤 3: 遍历所有可能的分割点，找到最小差值 ---
        long long min_difference = -1;

        // 分割点 i 的范围是 [n, 2n]
        // 第一部分从 nums[0...i-1] 选，第二部分从 nums[i...3n-1] 选
        for (int i = n; i <= 2 * n; ++i) {
            long long sum_first = prefix_min_sums[i - 1];
            long long sum_second = suffix_max_sums[i];
            
            long long current_diff = sum_first - sum_second;

            if (min_difference == -1 || current_diff < min_difference) {
                min_difference = current_diff;
            }
        }

        return min_difference;
    }
};

复杂度分析

• 时间复杂度:
  • 步骤 1 (计算前缀和)：遍历 3n 个元素，每次对优先队列操作，复杂度为 O(log n)。总时间为 O(n log n)。
  • 步骤 2 (计算后缀和)：同上，O(n log n)。
  • 步骤 3 (合并结果)：一个简单的 n 次循环，O(n)。
  • 总体时间复杂度为 O(n log n)。
• 空间复杂度:
  • 两个辅助数组 prefix_min_sum 和 suffix_max_sum，空间为 O(n)。
  • 两个优先队列，每个最多存储 n 个元素，空间为 O(n)。
  • 总体空间复杂度为 O(n)。