题目描述补充:
补数问题
补数是指两个数的和等于一个给定的数(通常是某个进制的基数,如十进制的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));
码小课网站中有更多相关内容分享给大家学习,包括但不限于算法基础、数据结构、面试技巧等,欢迎访问码小课获取更多知识。