题解 | #手套#

import java.util.*;

/**
 * 解题思路：（当每一种颜色的左手或者右手手套个数均大于零的时候）
 * 主要思路就是让一只手的手套每个颜色的都至少拿一只，之后另一只手随便拿一个就至少可以配对出一双手套，
 * 即求出左手手套个数为 leftSum ，其中个数最少的为 leftMin ，之后要满足左手手套每个颜色的都至少
 * 有一个的条件，即最少需要拿 leftSum-leftMin+1 个左手手套，之后右手手套再拿 1 个即可，而对应
 * 的另一种情况就是拿 rightSum-rightMin+1 ，之后再拿左手手套一个即可。
 * 即最少需要拿的手套数为 min(leftSum-leftMin+1 , rightSum-rightMin+1) + 1
 * (但是当存在左手或者右手手套个数为零的时候上述结论就不成立了，因为我们在拿 leftSum-leftMin+1
 * 个左手手套的时候，无法保证我们拥有每一种颜色的左手手套，因此这种情况下我们需要特殊处理）
 * 主要的思路就是我们再统计上述的 leftSum rightSum leftMin rightMin 的时候，略过那些只有一只手
 * 有手套，而另一只手没有手套的颜色的手套，最后在计算的时候，把这些特殊手套的总数加上即可，即这样子处理
 * 的本质就是先忽略掉这些特殊的手套，将那些非特殊的手套组合成一组，算出其中符合情况下最少需要拿的手套数，
 * 之后再考虑这些特殊的手套，比如加入个绿色的手套，只有左手 m 个，因此我们左手多拿 m 个就可以忽略掉这个
 * 绿色手套的干扰，因此最后的总数加上这些所有的特殊手套数即可。
 */
public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        int leftSum = 0;
        int rightSum = 0;
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MAX_VALUE;
        int sum = 0;  //记录特殊手套的数量
        for (int i = 0; i < n; i++) {
            if (left[i] * right[i] == 0) {
                sum += (left[i] + right[i]);
            } else {
                leftSum += left[i];
                rightSum += right[i];
                if (leftMin > left[i]) {
                    leftMin = left[i];
                }
                if (rightMin > right[i]) {
                    rightMin = right[i];
                }
            }
        }
        return Math.min(leftSum-leftMin+1,rightSum-rightMin+1) + sum + 1;
    }
}