1679. K 和数对的最大数目.md

1679. K 和数对的最大数目

• 哈希表

/**
 *
 * @complex T(n)/S(n)
 * @param {number[]} nums
 * @param {number} k
 * @return {*}  {number}
 */
function maxOperations(nums: number[], k: number): number {

    const map: Map<number, number> = new Map<number, number>();

    let count: number = 0;

    for (const num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
    }

    for (const [key1, value1] of map) {
        const key2: number = k - key1;
        if (key1 === key2) {
            count += map.get(key1);
        } else {
            count += Math.min(
                value1,
                map.get(key2) || 0,
            );
        }
    }

    return count >>> 1;
};

• 双指针

/**
 *
 * @complex T(nlogn)/S(1)
 * @param {number[]} nums
 * @param {number} k
 * @return {*}  {number}
 */
function maxOperations(nums: number[], k: number): number {

    nums.sort((a, b) => a - b);

    let leftIndex: number = 0,
        rightIndex: number = nums.length - 1,
        count: number = 0;

    while (leftIndex < rightIndex) {
        
        const current: number = nums[leftIndex] + nums[rightIndex];
        
        if(current === k) {
            ++count;
            ++leftIndex;
            --rightIndex;
        } else if(current > k) {
            --rightIndex;
        } else {
            ++leftIndex;
        }
    }

    return count;
};