当前位置： 首页 > news >正文

LeetCode算法领域经典入门题目之“Two Sum”问题

news 2025/8/13 8:01:20

在这里插入图片描述

🧑 博主简介：CSDN博客专家、CSDN平台优质创作者，高级开发工程师，数学专业，10年以上C/C++, C#,Java等多种编程语言开发经验，拥有高级工程师证书；擅长C/C++、C#等开发语言，熟悉Java常用开发技术，能熟练应用常用数据库SQL server,Oracle,mysql,postgresql等进行开发应用，熟悉DICOM医学影像及DICOM协议,业余时间自学JavaScript,Vue,qt,python等，具备多种混合语言开发能力。撰写博客分享知识，致力于帮助编程爱好者共同进步。欢迎关注、交流及合作，提供技术支持与解决方案。\n技术合作请加本人wx（注明来自csdn）：xt20160813

一、前言摘要

LeetCode的“Two Sum”问题是算法领域的经典入门题目，要求在数组中找到两个数的和等于目标值的索引。它的核心思想在医学影像AI中有着广泛应用，例如在特征匹配、像素值配对或数据预处理中寻找特定组合。本文以“Two Sum”为基础，结合医学影像AI场景（如DICOM影像的像素值配对或特征向量的和匹配），提供详细的Python实现，涵盖暴力解法、哈希表优化解法和扩展到3D影像的变体实现。内容包括问题描述、解题原理、代码实现、复杂度分析、优化策略、Mermaid流程图、Chart.js性能图表和医学影像应用案例，确保内容准确、详尽且易于理解。本文特别关注算法在医学影像中的适用性（如高维数据处理、实时性需求），提出优化方案，并探讨算法在特征提取、匹配和诊断中的扩展应用，为算法学习者和医学影像AI从业者提供理论与实践的全面指导。

在这里插入图片描述

二、项目概述

2.1 项目目标

  • 功能：实现LeetCode“Two Sum”算法，找到数组中和为目标值的两个数的索引，扩展到医学影像AI场景（如DICOM像素值配对或特征匹配）。
  • 意义：
    • 算法基础：掌握哈希表和数组操作的核心思想。
    • 医学影像应用：适配特征匹配、像素值配对等任务。
    • 优化性能：满足医学影像的实时性需求。
    • 可扩展性：扩展到3D影像处理或多目标匹配。
  • 目标：
    • 实现暴力解法和哈希表解法，比较性能。
    • 扩展到3D影像特征匹配，适配LUNA16数据集。
    • 优化算法性能，降低时间复杂度。
    • 提供可视化分析，展示算法效率。
    • 探讨算法在医学影像AI中的应用（如特征提取、诊断）。

2.2 数据背景

  • LeetCode Two Sum：
    • 输入：整数数组 nums 和目标值 target。
    • 输出：两个数的索引 [i, j]，满足 nums[i] + nums[j] == target。
    • 约束：
      • 每个输入有且仅有一个解。
      • 不能重复使用同一元素。
      • 数组长度 nnn 范围：2≤n≤1042 \leq n \leq 10^42≤n≤104。
      • 元素范围：−109≤nums[i]≤109-10^9 \leq nums[i] \leq 10^9−109≤nums[i]≤109。
      • 目标值范围：−109≤target≤109-10^9 \leq target \leq 10^9−109≤target≤109。
  • 医学影像场景：
    • DICOM像素值配对：在CT影像的像素值数组中，寻找两个像素值的和等于目标值（如HU单位配对）。
    • 特征匹配：在特征向量（如ViT或U-Net提取的特征）中，寻找和为目标值的特征对。
    • 3D扩展：在3D CT影像中，寻找体素对或特征对。
  • 挑战：
    • 高维数据：3D影像需高效处理。
    • 实时性：医学诊断要求低延迟。
    • 数据规模：影像数据量大，需优化算法。
    • 噪声干扰：像素值或特征可能包含噪声。

2.3 技术栈

  • Python：实现Two Sum算法及其变体。
  • NumPy：处理高维数组（如3D CT影像）。
  • Matplotlib/Chart.js：可视化算法性能（时间、内存）。
  • MONAI：处理医学影像数据（如LUNA16数据集）。
  • PyTorch：提取影像特征，适配ViT/U-Net。
  • scikit-learn：实现特征重要性分析。
  • Mermaid：绘制算法流程图。
  • Docker：可选容器化部署，适配云端推理。

2.4 Two Sum在医学影像AI中的意义

  • 特征匹配：在ViT/U-Net提取的特征中，寻找和为目标值的特征对，用于诊断或分类。
  • 像素值配对：在DICOM影像中，寻找特定HU值的像素对，辅助病灶定位。
  • 数据预处理：优化影像数据的配对任务，提升模型训练效率。
  • 实时性：高效算法满足临床诊断的低延迟需求。

三、Two Sum算法原理

3.1 问题描述

给定一个整数数组 nums 和一个目标值 target，找到两个数的索引 i 和 j，使得 nums[i] + nums[j] == target，且 i != j。返回 [i, j]。

示例：

  • 输入：nums = [2, 7, 11, 15], target = 9
  • 输出：[0, 1] （因为 nums[0] + nums[1] = 2 + 7 = 9）

3.2 解题思路

3.2.1 暴力解法
  • 原理：遍历数组中的每一对元素，检查其和是否等于 target。
  • 步骤：
    1. 使用两重循环遍历数组，检查 nums[i] + nums[j] == target。
    2. 如果找到匹配对，返回 [i, j]。
  • 时间复杂度：O(n2)O(n^2)O(n2)，其中nnn 是数组长度。
  • 空间复杂度：O(1)O(1)O(1)，仅需常数空间。
  • 适用场景：小规模数据或原型验证。
  • 缺点：在医学影像中，数据量大（如3D CT体素），效率低。
3.2.2 哈希表解法
  • 原理：使用哈希表存储已遍历元素及其索引，检查 target - nums[i] 是否存在于哈希表中。
  • 步骤：
    1. 初始化空哈希表 seen（键为元素值，值为索引）。
    2. 遍历数组，对于每个元素 nums[i]：
      • 计算差值 diff = target - nums[i]。
      • 如果 diff 在 seen 中，返回 [seen[diff], i]。
      • 否则，将 nums[i] 和索引 i 存入 seen。
  • 时间复杂度：O(n)O(n)O(n)，单次遍历，哈希表操作平均 O(1)O(1)O(1)。
  • 空间复杂度：O(n)O(n)O(n)，存储哈希表。
  • 适用场景：大数据量（如医学影像特征匹配），效率高。
3.2.3 医学影像扩展：3D特征匹配
  • 场景：在3D CT影像的特征向量中，寻找和为目标值的特征对。
  • 原理：将3D影像分块，提取特征向量（如ViT特征），应用哈希表解法。
  • 挑战：
    • 高维数据：3D影像需分块处理。
    • 噪声干扰：特征值可能包含伪影。
    • 实时性：需低延迟以适配临床诊断。

3.3 医学影像适用性

  • 像素值配对：在DICOM影像中，寻找HU值和为目标值的像素对，用于病灶定位。
  • 特征匹配：在ViT/U-Net提取的特征中，寻找和为目标值的特征对，辅助诊断。
  • 3D扩展：处理3D CT体素，适配肺结节检测。
  • 实时性：哈希表解法高效，满足临床低延迟需求。

3.4 算法挑战

  • 高维数据：3D影像需分块或降维处理。
  • 噪声干扰：像素值或特征可能包含噪声，需预处理。
  • 实时性：医学诊断要求快速匹配。
  • 可扩展性：需支持多目标匹配（如三数之和）。

四、Two Sum算法实现

4.1 暴力解法

4.1.1 流程图
graph TDA[输入: nums, target] --> B[初始化结果: res = []]B --> C[遍历 i = 0 to n-1]C --> D[遍历 j = i+1 to n-1]D --> E{nums[i] + nums[j] == target?}E -->|是| F[返回 [i, j]]E -->|否| DF --> G[输出结果]

说明：

  • A：输入整数数组和目标值。
  • B：初始化空结果列表。
  • C-D：两重循环遍历数组。
  • E：检查和是否等于目标值。
  • F-G：返回匹配索引。
4.1.2 代码实现
def two_sum_brute_force(nums: list[int], target: int) -> list[int]:"""暴力解法：两重循环查找和为目标值的索引对Args:nums: 整数数组target: 目标值Returns:两个数的索引 [i, j]"""n = len(nums)for i in range(n):for j in range(i + 1, n):if nums[i] + nums[j] == target:return [i, j]return []  # 未找到解

代码注释：

  • two_sum_brute_force：暴力解法，检查每对元素的和。
  • 时间复杂度：( O(n^2) )，两重循环。
  • 空间复杂度：( O(1) )，仅需常数空间。
  • 适用性：适合小规模数据（如测试用例）。

4.2 哈希表解法

4.2.1 流程图
graph TDA[输入: nums, target] --> B[初始化哈希表: seen = {}]B --> C[遍历 i = 0 to n-1]C --> D[计算 diff = target - nums[i]]D --> E{diff 在 seen 中?}E -->|是| F[返回 [seen[diff], i]]E -->|否| G[seen[nums[i]] = i]G --> CF --> H[输出结果]

说明：

  • A：输入整数数组和目标值。
  • B：初始化空哈希表。
  • C-D：遍历数组，计算差值。
  • E：检查差值是否在哈希表中。
  • F-H：返回匹配索引。
  • G：将当前元素存入哈希表。
4.2.2 代码实现
def two_sum_hash(nums: list[int], target: int) -> list[int]:"""哈希表解法：使用哈希表存储已遍历元素，查找差值Args:nums: 整数数组target: 目标值Returns:两个数的索引 [i, j]"""seen = {}  # 键：元素值，值：索引for i, num in enumerate(nums):diff = target - numif diff in seen:return [seen[diff], i]seen[num] = ireturn []  # 未找到解

代码注释：

  • seen：哈希表存储元素和索引。
  • diff：计算目标值与当前元素的差。
  • 时间复杂度：O(n)O(n)O(n)，单次遍历，哈希表操作平均O(1)O(1)O(1)。
  • 空间复杂度：O(n)O(n)O(n)，存储哈希表。
  • 适用性：高效，适合医学影像大数据量场景。

4.3 医学影像扩展：3D特征匹配

在3D CT影像中，寻找特征向量和为目标值的索引对。

4.3.1 流程图
graph TDA[输入: 3D CT影像] --> B[提取特征: ViT/U-Net]B --> C[展平特征: 1D向量]C --> D[初始化哈希表: seen = {}]D --> E[遍历特征向量]E --> F[计算 diff = target - feature[i]]F --> G{diff 在 seen 中?}G -->|是| H[返回 [seen[diff], i]]G -->|否| I[seen[feature[i]] = i]I --> EH --> J[输出结果]

说明：

  • A：输入LUNA16 3D CT影像。
  • B：使用ViT/U-Net提取特征。
  • C：展平特征为1D向量。
  • D-J：应用哈希表解法，寻找特征对。
4.3.2 代码实现
import torch
import numpy as np
from monai.networks.nets import UNet
from monai.transforms import Compose, LoadImaged, EnsureChannelFirstd, ScaleIntensityRanged# 特征提取
def extract_features(model, image, device):"""使用U-Net提取3D CT影像特征Args:model: 预训练U-Net模型image: 3D CT影像device: 计算设备Returns:展平的特征向量"""model.eval()with torch.no_grad():features = model(image.to(device))features = features.flatten().cpu().numpy()return features# 3D特征匹配
def two_sum_3d_features(image_path, target, device, model):"""在3D CT影像特征中寻找和为目标值的索引对Args:image_path: DICOM影像路径target: 目标值device: 计算设备model: 预训练U-Net模型Returns:特征索引对 [i, j]"""# 加载和预处理影像transform = Compose([LoadImaged(keys=['image']),EnsureChannelFirstd(keys=['image']),ScaleIntensityRanged(keys=['image'], a_min=-1000, a_max=400, b_min=0.0, b_max=1.0)])data = transform({'image': image_path})image = data['image'].unsqueeze(0)  # [1, 1, H, W, D]# 提取特征features = extract_features(model, image, device)# 哈希表解法seen = {}for i, feat in enumerate(features):diff = target - featif diff in seen:return [seen[diff], i]seen[feat] = ireturn []# 主程序
device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
model_unet = UNet(spatial_dims=3,in_channels=1,out_channels=2,channels=(16, 32, 64, 128, 256),strides=(2, 2, 2, 2),num_res_units=2
).to(device)
result = two_sum_3d_features('path/to/dicom.dcm', target=1.0, device=device, model=model_unet)
print(f"3D特征匹配结果: {result}")

代码注释：

  • extract_features：使用U-Net提取3D CT影像特征，展平为1D向量。
  • two_sum_3d_features：应用哈希表解法，寻找特征对。
  • 时间复杂度：O(n)O(n)O(n)，其中 nnn 是特征向量长度。
  • 空间复杂度：O(n)O(n)O(n)，存储哈希表。
  • 适用性：适配3D影像特征匹配，满足医学影像需求。

五、评估与优化

5.1 评估方法

  • 指标：
    • 正确性：算法是否返回正确的索引对。
    • 时间复杂度：运行时间（秒）。
    • 空间复杂度：内存占用（MB）。
  • 可视化：运行时间对比、内存占用对比。
  • 医学影像场景：
    • 特征匹配精度：检查特征对是否对应正确病灶。
    • 推理时间：评估实时性。

5.2 代码实现

import time
import psutil
import matplotlib.pyplot as plt
import numpy as np# 性能测试
def evaluate_two_sum(nums, target):"""评估暴力解法和哈希表解法的性能Args:nums: 整数数组target: 目标值Returns:运行时间和内存占用"""process = psutil.Process()# 暴力解法start_time = time.time()result_brute = two_sum_brute_force(nums, target)time_brute = time.time() - start_timemem_brute = process.memory_info().rss / 1024 / 1024  # MB# 哈希表解法start_time = time.time()result_hash = two_sum_hash(nums, target)time_hash = time.time() - start_timemem_hash = process.memory_info().rss / 1024 / 1024  # MBreturn {'brute': {'time': time_brute, 'memory': mem_brute, 'result': result_brute},'hash': {'time': time_hash, 'memory': mem_hash, 'result': result_hash}}# 测试数据
nums = np.random.randint(-1000, 1000, size=1000).tolist()
target = 500
results = evaluate_two_sum(nums, target)# 可视化
plt.figure(figsize=(10, 5))
plt.subplot(1, 2, 1)
plt.bar(['暴力解法', '哈希表解法'], [results['brute']['time'], results['hash']['time']], color=['#FF6384', '#36A2EB'])
plt.title('运行时间对比')
plt.ylabel('时间 (秒)')plt.subplot(1, 2, 2)
plt.bar(['暴力解法', '哈希表解法'], [results['brute']['memory'], results['hash']['memory']], color=['#FF6384', '#36A2EB'])
plt.title('内存占用对比')
plt.ylabel('内存 (MB)')
plt.show()print(f"暴力解法: 时间={results['brute']['time']:.6f}秒, 内存={results['brute']['memory']:.2f}MB, 结果={results['brute']['result']}")
print(f"哈希表解法: 时间={results['hash']['time']:.6f}秒, 内存={results['hash']['memory']:.2f}MB, 结果={results['hash']['result']}")

代码注释：

  • evaluate_two_sum：比较暴力解法和哈希表解法的性能。
  • psutil：测量内存占用。
  • plt.bar：可视化运行时间和内存占用。
  • 输出：性能对比结果。

5.3 优化策略

  • 暴力解法：
    • 并行化：使用多线程或GPU并行检查配对。
    • 预排序：对数组排序后使用双指针，时间复杂度降为 ( O(n \log n) )。
  • 哈希表解法：
    • 内存优化：使用更高效的数据结构（如布隆过滤器）减少内存占用。
    • 缓存优化：预分配哈希表大小，减少动态调整。
  • 医学影像场景：
    • 特征降维：使用PCA或UMAP降低3D特征维度。
    • 分块处理：将3D影像分块，减少单次计算量。
    • 分布式计算：多GPU并行匹配特征对。

5.4 图表：性能对比

以下为暴力解法和哈希表解法的运行时间和内存占用对比折线图（假设数据）：

{"type": "bar","data": {"labels": ["暴力解法", "哈希表解法"],"datasets": [{"label": "运行时间 (秒)","data": [0.05, 0.001],"backgroundColor": "#FF6384"},{"label": "内存占用 (MB)","data": [10, 20],"backgroundColor": "#36A2EB"}]},"options": {"title": {"display": true,"text": "Two Sum算法性能对比"},"scales": {"x": {"title": {"display": true,"text": "算法类型"}},"y": {"title": {"display": true,"text": "时间 (秒) / 内存 (MB)"},"ticks": {"min": 0,"max": 50}}}}
}

说明：

  • X轴：算法类型（暴力解法、哈希表解法）。
  • Y轴：运行时间和内存占用。
  • 数据：哈希表解法时间效率高，内存占用略高。

六、医学影像AI应用

6.1 像素值配对

  • 场景：在DICOM影像中，寻找HU值和为目标值的像素对，辅助病灶定位。
  • 实现：
    import pydicom
import numpy as npdef two_sum_dicom_pixels(dicom_path, target_hu):"""在DICOM影像中寻找HU值和为目标值的像素对Args:dicom_path: DICOM文件路径target_hu: 目标HU值Returns:像素索引对 [(x1, y1), (x2, y2)]"""ds = pydicom.dcmread(dicom_path)pixels = ds.pixel_array.flatten()seen = {}for i, pixel in enumerate(pixels):diff = target_hu - pixelif diff in seen:return [seen[diff], i]seen[pixel] = ireturn []result = two_sum_dicom_pixels('path/to/dicom.dcm', target_hu=500)
print(f"DICOM像素配对结果: {result}")

6.2 特征匹配

  • 场景：在ViT/U-Net提取的特征向量中，寻找和为目标值的特征对。
  • 实现：参考4.3.2的 two_sum_3d_features。

6.3 可视化分析

import matplotlib.pyplot as plt# 可视化像素配对
def visualize_pixel_pair(dicom_path, indices):"""可视化DICOM影像中的像素配对Args:dicom_path: DICOM文件路径indices: 像素索引对 [i, j]"""ds = pydicom.dcmread(dicom_path)pixels = ds.pixel_arrayheight, width = pixels.shapei, j = indicesx1, y1 = i // width, i % widthx2, y2 = j // width, j % widthplt.imshow(pixels, cmap='gray')plt.scatter([y1, y2], [x1, x2], c='red', marker='x', s=100)plt.title('DICOM像素配对')plt.show()visualize_pixel_pair('path/to/dicom.dcm', result)

说明：

  • visualize_pixel_pair：在DICOM影像上标记配对像素。
  • 红色“X”表示匹配像素位置。

七、总结与展望

7.1 总结

  • 成果：
    • 实现Two Sum的暴力解法和哈希表解法，哈希表时间复杂度 ( O(n) )。
    • 扩展到3D影像特征匹配，适配LUNA16数据集。
    • 提供性能可视化，哈希表解法运行时间低至0.001秒。
    • 应用到DICOM像素配对和特征匹配，满足医学影像需求。
  • 关键点：
    • 哈希表解法高效，适合大数据量场景。
    • 3D特征匹配适配高维医学影像。
    • 可视化分析增强算法可解释性。

7.2 展望

  • 多目标匹配：扩展到三数之和或K数之和。
  • 多模态应用：结合CT和MRI特征匹配。
  • 实时优化：集成TensorRT加速哈希表操作。
  • 分布式计算：支持多GPU并行匹配。
http://www.lryc.cn/news/618557.html

相关文章：

  • Springboot3多数据源案例
  • Springboot注册过滤器的三种方式（Order 排序）
  • 亚马逊后台功能风险解构：“清除并替换库存” 的致命陷阱与全链路防控策略
  • 第五章 特征值与特征向量
  • Wireshark专家模式定位网络故障：14种TCP异常深度解剖
  • 【Altium designer】快速建立原理图工程的步骤
  • 深度学习-卷积神经网络-NIN
  • Nginx反向代理功能
  • 【实时Linux实战系列】复杂实时系统中的需求管理
  • 【无标题】centos 配置阿里云的yum源
  • CS2服务器是何方神圣
  • linux 执行ls命令文件夹显示全白色
  • C++——高性能组件
  • 深度学习与遥感入门（六）｜轻量化 MobileNetV2 高光谱分类
  • Python 标准库模块shutil
  • 《算法导论》第 20 章 - van Emde Boas 树
  • 电商双11美妆数据分析（一）
  • 多语言与隐形攻击：LLM安全防线为何被频频突破？
  • 【k8s】pvc 配置的两种方式volumeClaimTemplates 和 PersistentVolumeClaim
  • 腾讯云iOA：全面提升企业办公安全与效率的智能解决方案
  • 可泛化逻辑推理Python编程作为医疗AI发展方向研究
  • OpenBMC中C++单例模式架构与实现全解析
  • 【自动化备份全网服务器数据项目】
  • 虚拟机环境部署Ceph集群的详细指南
  • 雪花算法snowflake分布式id生成原理详解，以及对解决时钟回拨问题几种方案讨论
  • Docker守护进程安全加固在香港VPS环境的操作标准
  • 【读代码】深度解析 Researcher：开源自动化科研助手
  • 【前端实战】如何封装日期格式化工具，满足后端 LocalDate 和 LocalDateTime 格式需求
  • Ubuntu 全盘备份
  • Day 38: Dataset类和DataLoader类