如何在超45万条数据中找出4条总和为$15.68的记录

一、示例数据的符合条件记录 #

将示例中金额转换为数值计算后，确认最后4条记录的金额总和恰好为$15.68，具体记录如下：

ID     Amount
111    $4.44
122    $5.00
133    $4.00
144    $2.24

计算验证：4.44 + 5.00 + 4.00 + 2.24 = 15.68

二、45万条大规模数据集的处理方案 #

暴力枚举所有4条记录的组合（复杂度O(n⁴)）完全不可行，必须采用优化策略：

1. 预处理步骤 #

• 将Amount列的带$字符串格式转换为数值类型，方便计算；
• 为数据集的ID和Amount字段建立索引，加快查找速度。

2. 优化算法思路 #

方法A：分治+哈希表（Python实现）

通过拆分问题降低复杂度，将四数之和转化为两组两数之和的匹配：

• 第一步：计算所有两两记录的金额和，存储为(两数和, ID1, ID2)格式，存入哈希表（键为和值，值为对应ID对列表）；
• 第二步：遍历所有两两记录的金额和，计算目标差值15.68 - 当前两数和，在哈希表中查找是否存在该差值对应的ID对；
• 第三步：确保找到的四个ID互不重复（每条记录唯一），收集去重后的符合条件组合。

示例代码片段：

import pandas as pd
from collections import defaultdict

# 读取数据集（假设为CSV格式）
df = pd.read_csv('your_dataset.csv')
# 转换金额为数值
df['Amount'] = df['Amount'].str.replace('$', '').astype(float)

# 生成两两和的哈希表
pair_sum_map = defaultdict(list)
n = len(df)
for i in range(n):
    for j in range(i+1, n):
        sum_ab = df['Amount'].iloc[i] + df['Amount'].iloc[j]
        pair_sum_map[sum_ab].append((df['ID'].iloc[i], df['ID'].iloc[j]))

# 查找符合条件的四元组
target = 15.68
result = set()
for i in range(n):
    for j in range(i+1, n):
        sum_cd = df['Amount'].iloc[i] + df['Amount'].iloc[j]
        needed = target - sum_cd
        if needed in pair_sum_map:
            for (id_a, id_b) in pair_sum_map[needed]:
                # 确保四个ID互不重复
                ids = {id_a, id_b, df['ID'].iloc[i], df['ID'].iloc[j]}
                if len(ids) == 4:
                    # 按ID排序去重，避免重复组合
                    sorted_ids = tuple(sorted(ids))
                    result.add(sorted_ids)

# 输出结果对应的记录
for ids in result:
    print(df[df['ID'].isin(ids)])

方法B：SQL优化查询（数据库存储场景）

若数据存储在关系型数据库中，可通过多表连接+条件过滤实现，利用数据库索引优化性能：

-- 假设表名为transactions，字段为ID（INT）、Amount（DECIMAL(10,2)）
SELECT t1.ID, t1.Amount, t2.ID, t2.Amount, t3.ID, t3.Amount, t4.ID, t4.Amount
FROM transactions t1
JOIN transactions t2 ON t2.ID > t1.ID
JOIN transactions t3 ON t3.ID > t2.ID
JOIN transactions t4 ON t4.ID > t3.ID
WHERE t1.Amount + t2.Amount + t3.Amount + t4.Amount = 15.68;

注：使用ID > 前一个ID的条件可避免重复组合（如t1,t2,t3,t4与t2,t1,t3,t4视为同一组合），同时减少查询量。建议提前为Amount字段建立索引。

3. 额外优化建议 #

• 若存在大量重复金额，可先去重并记录出现次数，减少计算量；
• 提前过滤极端值（如金额远大于15.68或远小于负数阈值），缩小数据集范围；
• 若仅需任意一组符合条件的记录，找到第一组后即可终止计算，节省资源。

内容的提问来源于stack exchange，提问作者programmerNOOB