To solve this problem, we need to find the maximum number of pairs in an array that sum up to a given target value. Each element can be used in at most one pair.

Approach

The key insight here is to use a frequency dictionary to count occurrences of each number in the array. This allows us to efficiently determine how many valid pairs we can form:

1. Count Frequencies: Use a frequency counter to keep track of how many times each number appears in the array.
2. Calculate Pairs:
   • For a number x, if x equals target - x (e.g., target=4 and x=2), the number of pairs is the integer division of the frequency of x by 2 (since each pair uses two instances of x).
   • If x is less than target - x (to avoid double-counting pairs like (1,3) and (3,1)), the number of pairs is the minimum of the frequency of x and the frequency of target - x.

Solution Code

from collections import Counter

def max_pairs(nums, target):
    freq = Counter(nums)
    pairs = 0
    for x in freq:
        complement = target - x
        if x == complement:
            pairs += freq[x] // 2
        elif x < complement:
            pairs += min(freq[x], freq.get(complement, 0))
    return pairs

Explanation

Let’s break down the solution with examples:

1. Example 1: nums = [1,2,3,4], target=5

   • Frequencies: {1:1,2:1,3:1,4:1}
   • For x=1, complement=4 → min(1,1)=1 pair.
   • For x=2, complement=3 → min(1,1)=1 pair.
   • Total pairs: 2.

2. Example 2: nums = [2,2,2,2], target=4

   • Frequencies: {2:4}
   • x=2 equals complement → 4//2=2 pairs.
   • Total pairs: 2.

3. Example3: nums = [3,1,3,4,3], target=6

   • Frequencies: {3:3,1:1,4:1}
   • x=3 equals complement →3//2=1 pair.
   • Total pairs: 1.

This approach efficiently computes the result in O(n) time complexity (due to counting frequencies and iterating over unique elements), making it suitable for large arrays. The space complexity is O(n) for storing the frequency counter.

Answer: The function max_pairs returns the maximum number of valid pairs. For example, if the input is nums = [1,2,3,4] and target=5, the output is 2. The final answer is the code provided above.

from collections import Counter

def max_pairs(nums, target):
    freq = Counter(nums)
    pairs = 0
    for x in freq:
        complement = target - x
        if x == complement:
            pairs += freq[x] // 2
        elif x < complement:
            pairs += min(freq[x], freq.get(complement, 0))
    return pairs

作者声明:本文包含人工智能生成内容。