https://leetcode.com/problems/array-partition-i/#/description

image.png

image.png

翻譯

• 將長(zhǎng)度為2n的數(shù)組分為n組,每組2個(gè)元素稱為一個(gè)pair
• 將所有pair中較小的那個(gè)元素取出來,并求和
• 如何使得求和結(jié)果最大?即如何劃分pair

思路

• min[列表最小元素, 任意元素] = 列表最小元素(注意不受任意元素的影響)
• 那么sum(min[ ], min[]...)與任意元素?zé)o關(guān)
• 為了使得sum最大, 每個(gè)pair中的任意元素也要小一些,這樣使得較大的元素不會(huì)被"淹沒掉"進(jìn)而能對(duì)sum做出較大的貢獻(xiàn)
• 對(duì)數(shù)組進(jìn)行排序, min[array[i], array[i+1]] = array[i]
• 所以只要對(duì)排序后的數(shù)組每隔以為取元素求和即可

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(sorted(nums)[::2])