求解满足条件的元素对个数问题:给定N个整数A,以及一个正整数C,问其中有多少对满足Ai-Aj=C。
时间: 2024-10-11 13:15:19 浏览: 25
求解这个问题通常涉及到集合和哈希表的数据结构。你可以使用以下步骤:
1. **创建哈希表**:遍历数组A,对于每个元素`Ai`,检查`Ai+C`是否也在数组中。如果在,那么就将`Ai+C`作为键(key),它的出现次数作为值(value)存储在哈希表中。
2. **计数匹配对**:再遍历一次数组A,这次同时查找当前元素`Ai`及其目标差值`C`在哈希表中的对应值。如果有,说明找到了一对满足条件的元素`(Ai, Ai+C)`,然后减去这个值以防止重复计算(因为同一个对可能有重复计数)。如果没有,就直接跳过。
3. **结果累加**:遍历结束后,哈希表中存储的就是所有满足条件的元素对的数量。注意这里的“满足”是指至少有一对元素之差等于`C`。
```python
def count_pairs(A, C):
count = 0
hash_table = {}
# 第一遍填充哈希表
for i in A:
if i + C in hash_table:
count += hash_table[i + C]
if i in hash_table:
hash_table[i] += 1
else:
hash_table[i] = 1
# 第二遍统计匹配对
for i in A:
if i - C in hash_table:
count += hash_table[i - C]
return count
# 示例
A = [1, 7, 5, 9, 2, 6]
C = 4
print(count_pairs(A, C)) # 输出:4
```
阅读全文