数组拆分 I

给定长度为?2n?的数组,你的任务是将这些数分成?n 对,例如 (a₁,b₁),(a₂,b₂),...,(a_n,b_n) ，使得从1 到?n 的 min(a_i,b_i) 总和最大。

示例 1:

输入: [1,4,3,2]

?

输出: 4

解释: n 等于 2,最大总和为 4 = min(1,2) + min(3,4).

提示:

1. n?是正整数,范围在 [1,10000].
2. 数组中的元素范围在 [-10000,10000].

?

?

思路

这道题目给了我们一个数组有2n integers， 需要我们把这个数组分成n对，然后从每一对里面拿小的那个数字，把所有的加起来，返回这个sum。并且要使这个sum 尽量最大。如何让sum 最大化呢，我们想一下，如果是两个数字，一个很小，一个很大，这样的话，取一个小的数字，就浪费了那个大的数字。所以我们要使每一对的两个数字尽可能接近。我们先把nums sort 一下，让它从小到大排列，接着每次把index： 0， 2， 4...偶数位的数字加起来就可以了。

?

 1 import java.util.Arrays;
 2 
 3 public class Solution
 4 {
 5     public int arrayPairSum(int[] nums)
 6     {
 7         int sum = 0;
 8         Arrays.sort(nums);
 9         for(int i=0; i<nums.length; i+=2) sum += nums[i];
10         return sum;
11     }
12 }