Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

1.排序+贪心，要使n对整数的每对的最小值的和最大，就需要先排序，然后相邻两个数组成一对。例如，a1 < a2 < a3 < a4

min(a1, a2) + min(a3, a4) = a1 + a3, 换一种组合方式就是a1 + a2。

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);

        int res = 0;
        for(int i = 0; i < nums.length - 1; i += 2) {
            res += nums[i];
        }

        return res;
    }
}

2.另一种做法理论上可以把时间复杂度缩小到O(n)，但是对于leetcode上的testcase也许运行时间会比第一种方法长一些。首先，题目给定了数组中元素的范围[-10000, 10000]。这样的话我们就可以省去排序的过程，直接统计每个元素出现的次数来代替排序。由于元素可能是负数，我们可以设定一个+10000的offset，来把元素map到一个数组中相应位置（num[n + 10000]）。在求和的时候，只要知道每个数和这个数应该使用的次数就可以了。

接下来的问题就是如何统计一个数被使用的次数。一个数使用的次数取决于两个因素：1）之前一个数出现次数的奇偶性 2）当前数出现次数的奇偶性。我们可以用一个变量left记录上一个数被使用的情况（例如[1 1 1 2]，配对应为[1 1] [1 2]），奇数时left为1（例子中有一个1用来与2配对），偶数时left为0（例如[1 1 2 2]的配对为[1 1] [2 2]）。于是当前的数被使用的次数为(count[n + offset] + 1 - left) / 2，再记录当前的数对应的left值，应为(count[n + offset] - left) % 2,但是考虑到对于没有出现过的数字，这个结果可能为负值，为了避免这个情况我们可以将其修改为正数，(count[n + offset] - left + 2) % 2

class Solution {
    public int arrayPairSum(int[] nums) {
        int[] count = new int[20001];
        int offset = 10000;
        for(int n: nums) {
            count[n + offset]++;
        }

        int res = 0;
        int left = 0;

        for(int i = - 10000; i <= 10000; i++) {
            res += (count[i + offset] + 1 - left) / 2 * i;
            left = (count[i + offset] - left + 2) % 2;
        }

        return res;
    }
}