Problem

给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数(不同位置的数字一样的数对算不同的数对).

Approach

在数列中查找B,使B+C=A.

题目的标签是二分查找,当然想着从这个角度思考.

int binaryFind(const vector<int>& numbers,int C){
    int count=0;
    for (int b=0;b<numbers,size(),b++){
        int ans=numbers[b]+C;
        int left=0,right=numbers.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(numbers[mid]==ans){
                count++;
                break;//跳出while循环
            }
            else if(numbers[mid]<ans) left=mid+1;
            else right=mid-1;
        }
    }
    return count;
}

局部变量的作用范围（scope）应该与它的使用需求一致。每轮查找都要重置ans,left,right,所以都要定义在while循环里面.例如:如果把 left 和 right 定义在 for 循环外, left 和 right 不会重置，当某次查找中 left 被移动到 numbers.size()，下一次查找直接从这个值开始，二分查找就完全无效了。

实际上函数并不满足题干的提示内容.因为每次找到符合的数对都会立刻跳出循环,但这个数可能存在多个.

解决:向前和向后遍历.

if (numbers[mid]==ans){
    count++;
    int l=mid-1;
    while(l>0&&numbers[l]==ans){
        count++;
        l--;
    }
    int r=mid+1;
    while(r<numbers.size()&&numbers[r]==ans){
        count++;
        r++;
    }
    break;
}

为什么if循环要加break语句?因为其判断条件

哈希表

Introduce

思考一下函数的定义:

基本概念

键（Key）：
- 数据的标识符，用来定位存储的位置。键可以是字符串、整数等。
- 例如，key = "name"。
值（Value）：
- 键对应的数据内容。
- 例如，value = "Alice"。
哈希函数（Hash Function）：
- 一个函数，用于将键映射到一个数组中的索引（Index）。
- 例如，hash("name") = 5，表示 "name" 存储在数组索引 5 的位置。
哈希冲突（Hash Collision）：
- 不同的键通过哈希函数可能映射到相同的索引，这称为冲突。
- 解决方法包括链地址法（Chaining）\和*开放地址法（Open Addressing）*。

操作

插入（Insertion）：

将一个键值对插入到表中。平均时间复杂度 O(1)。
例如，table["name"] = "Alice"。

查找（Search）：

根据键找到对应的值。平均时间复杂度 O(1)。
例如，table["name"] 返回 "Alice"。

删除（Deletion）：

从哈希表中移除某个键值对。平均时间复杂度 O(1)。
例如，table.erase("name")。

特点

优点：
- 快速操作：查找、插入和删除操作平均时间复杂度都是 O(1)。
- 键值对存储：非常适合需要通过键快速定位值的数据结构。
- 灵活性：键可以是任意类型（如字符串、整数）。
缺点：
- 内存占用高：需要为哈希表分配更多的空间来避免冲突。
- 哈希冲突问题：可能会导致效率降低。
- 无序性：大多数哈希表无法保证存储顺序。

实际应用场景

词频统计
- 统计文章中每个单词的出现次数。
缓存（Cache）
- 例如，LRU Cache 利用哈希表快速查找缓存内容。
数据库索引
- 用哈希表快速定位记录。
图论问题
- 在图的邻接表中，用哈希表存储邻接关系。

之前的问题

现在用哈希表实现最开始的问题

#include <unordered_map>
int countPairs(const vector<int>& numbers, int C){
    unordered_map<int,int> freq;
    int count=0;
    for (int num:numbers){
        freq[num]++;
    }
    for (int num:numbers){
        int target = num + C;  // b + C = a
        if (freq.count(target)) {  // 检查目标值是否存在
            count += freq[target];  // 统计所有重复值
        }
    }
    return count;
}

二分与哈希表