当前位置: 面试刷题>> 补数 (经典算法题500道)


题目描述补充:

补数问题

补数是指两个数的和等于一个给定的数(通常是某个进制的基数,如十进制的10,二进制的2等)。在这个问题中,我们要求在给定的一个非负整数数组中,找出所有和为特定值(比如十进制下的10)的整数对(两个数组成的对)。数组中的每个元素只能使用一次,且不考虑顺序(即[a, b]和[b, a]视为相同的对)。

示例

给定数组 [1, 7, 5, 3, 4, 2] 和目标和 10,函数应返回 [[1, 9], [2, 8], [3, 7], [4, 6], [5, 5]]。但注意,由于题目限定数组为 [1, 7, 5, 3, 4, 2],且每个元素只能使用一次,因此实际上返回的是 [[1, 9], [7, 3], [4, 6], [5, 5]] 是不正确的,因为9和8并不在数组中。正确的返回应该是 [[1, 9] 转换为 [7, 3], [4, 6](实际不存在,仅为说明), [5, 5]] 中的有效对,即 [[7, 3], [5, 5]](注意[1, 9]不是有效对,因为9不在数组中,这里仅用于解释补数概念)。但按照原数组,应为 [[7, 3], [5, 5]]

PHP 示例代码

function findComplementPairs($nums, $target) {
    $result = [];
    $numMap = [];
    
    // 使用哈希表存储每个数字是否出现过
    foreach ($nums as $num) {
        $numMap[$num] = true;
    }
    
    // 遍历数组,查找补数
    foreach ($nums as $num) {
        $complement = $target - $num;
        if (isset($numMap[$complement]) && $complement != $num) {
            // 排除自己与自己配对的情况,并添加结果
            $result[] = [$num, $complement];
        } elseif ($complement == $num && isset($numMap[$complement])) {
            // 如果补数就是本身,且确实存在,则添加一次
            $result[] = [$num, $complement];
            unset($numMap[$complement]); // 避免重复添加
        }
    }
    
    return $result;
}

// 测试代码
$nums = [1, 7, 5, 3, 4, 2];
$target = 10;
print_r(findComplementPairs($nums, $target));

Python 示例代码

def find_complement_pairs(nums, target):
    num_set = set(nums)
    result = []
    
    for num in nums:
        complement = target - num
        if complement in num_set and complement != num:
            result.append([num, complement])
        elif complement == num:
            result.append([num, complement])
            num_set.remove(complement)  # 避免重复添加
    
    return result

# 测试代码
nums = [1, 7, 5, 3, 4, 2]
target = 10
print(find_complement_pairs(nums, target))

JavaScript 示例代码

function findComplementPairs(nums, target) {
    const numSet = new Set(nums);
    const result = [];
    
    for (let num of nums) {
        const complement = target - num;
        if (numSet.has(complement) && complement !== num) {
            result.push([num, complement]);
        } else if (complement === num && numSet.has(complement)) {
            result.push([num, complement]);
            numSet.delete(complement); // 避免重复添加
        }
    }
    
    return result;
}

// 测试代码
const nums = [1, 7, 5, 3, 4, 2];
const target = 10;
console.log(findComplementPairs(nums, target));

码小课网站中有更多相关内容分享给大家学习,包括但不限于算法基础、数据结构、面试技巧等,欢迎访问码小课获取更多知识。

推荐面试题