感觉这道题的精髓是下面两点：

  • n = sum(a1...an) - a1 + 1 （n 从 a1 到 an 中拿到每一个种类至少要拿的总数。a1 到 an 是递增的，表示不同种类）
  • 如果左右手套出现 0 应该如何处理

题解 :

对于非0递增序列a1,a2...an，要想最终取值覆盖每一个种类
n = sum(a1...an) - a1 + 1（也就是总数减去最小值之后加一）
所以对于左右手手套颜色都有数量的序列，想要覆盖每一种颜色，则最小数量leftsum = 左边数量
和 - 左边最小值 + 1， rightsum = 右边数量和 - 右边的最小值 + 1。而对于有0存在的，则需要做
累加，保证覆盖每一种颜色。

就以题目的例子为例：

min(left_sum - left_min + 1, right_sum - right_min + 1) 是 7
left_sum - left_min + 1 是 12
right_sum - right_min + 1 是 7
sum 是 2

sum 中 left 为 0 加进来的总数（1）表示应该从 right 中多拿的手套数

right 为 0，加进来的总数（1），表示应该从 left 中多拿的手套数

我们在做 n = sum(a1...an) - a1 + 1 运算时忽略左右任意一方为 0 的那个颜色。

class Gloves {
public:
    int findMinimum(int n, vector<int> left, vector<int> right) {
        int leftSum = 0, rightSum = 0;
        int leftMin = INT_MAX, rightMin = INT_MAX;
        int complete = 0; //需要从左右手套中多拿的数量
        for(int i = 0; i < n; i++)
        {
            if(left[i] * right[i] == 0)
                complete += (left[i] + right[i]);
            else 
            {
                leftSum += left[i];
                rightSum += right[i];
                leftMin = min(leftMin, left[i]);
                rightMin = min(rightMin, right[i]);
            }
        }
        return complete + min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1;
    }
};

给大家推荐我的刷题总结仓库，会持续更新，有兴趣的朋友可以加入我~我们一起互相监督
https://github.com/hairrrrr/1200_Problems