給定長度為 2n 的整數數組 nums ,你的任務是將這些數分成 n 對, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得從 1 到 n 的 min(ai, bi) 總和最大。
返回該 最大總和 。
示例 1:
輸入:nums = [1,4,3,2]
輸出:4
解釋:所有可能的分法(忽略元素順序)為:
- (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
- (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
- (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大總和為 4
解題思路
每個數字對的兩個元素越接近,那么min(ai, bi) 總和最大
代碼
class Solution {public int arrayPairSum(int[] nums) {int res=0;Arrays.sort(nums);for (int i = 0; i < nums.length; i+=2) {res+= Math.min(nums[i],nums[i+1]);}return res;}
}