两数之和函数效率差异分析：时间复杂度与优化方案问询

1. twosum2和twosum3的循环次数 #

基于常见的实现逻辑：

• twosum2：通常是单循环遍历所有n个元素，每次循环内查找互补值，最多循环n次，但循环内包含额外的查找操作。
• twosum3：一般分两步执行——先遍历n个元素构建哈希表，再遍历n个元素查找互补值，最多循环2n次，总循环次数为线性量级，但存在两次遍历的叠加开销。

2. 时间复杂度计算 #

• twosum2：若使用R基础的match或%in%做互补值查找，这类操作的时间复杂度为O(n)，因此总时间复杂度是O(n)（循环次数）× O(n)（单次查找）= O(n²)，和twosum1的理论复杂度一致，但常数项开销不同。
• twosum3：构建哈希表的时间为O(n)，每次哈希查找的理论时间复杂度为O(1)，因此总时间复杂度是O(n)（构建哈希表）+ O(n)（遍历查找）= O(n)，属于线性复杂度。

3. 为何twosum2、twosum3执行速度更慢 #

虽然理论复杂度twosum3更优，但实际运行速度受R语言的特性限制：

• twosum2：每次循环内的match是内置函数，但存在函数调用、向量切片（如nums[-i]）和索引修正的额外开销，这些常数项开销累加后，比twosum1的嵌套纯循环（仅做简单索引访问和加法判断）更耗时。
• twosum3：R中的environment（哈希实现）操作效率不高，且需要将数值转为字符串作为键，额外增加了类型转换开销；两次遍历的总常数开销，加上哈希表的维护成本，反而抵消了线性复杂度的优势，导致实际速度不如twosum1。

4. 优化方法 #

方法1：双指针法（基于排序） #

利用排序+双指针将时间复杂度降到O(n log n)，依赖R高效的内置排序实现，避免循环内的高开销操作：

twosum_opt双指针 <- function(nums, target) {
  sorted_idx <- order(nums)
  sorted_nums <- nums[sorted_idx]
  left <- 1
  right <- length(sorted_nums)
  while (left < right) {
    current_sum <- sorted_nums[left] + sorted_nums[right]
    if (current_sum == target) {
      return(sort(c(sorted_idx[left], sorted_idx[right])))
    } else if (current_sum < target) {
      left <- left + 1
    } else {
      right <- right - 1
    }
  }
  NULL
}

方法2：使用高效查找工具替代基础查找 #

用fastmatch包的fmatch函数（比基础match快数倍）优化twosum2：

library(fastmatch)
twosum_opt_fastmatch <- function(nums, target) {
  n <- length(nums)
  for (i in 1:n) {
    complement <- target - nums[i]
    j <- fmatch(complement, nums, nomatch = 0)
    if (j != 0 && j != i) {
      return(c(i, j))
    }
  }
  NULL
}

方法3：Rcpp实现哈希查找 #

用C++的std::unordered_map实现高效哈希操作，彻底规避R语言的哈希开销：

# 先安装并加载Rcpp包
# install.packages("Rcpp")
library(Rcpp)
cppFunction('
IntegerVector twosum_rcpp(NumericVector nums, double target) {
  std::unordered_map<double, int> hash_map;
  int n = nums.size();
  for (int i = 0; i < n; ++i) {
    hash_map[nums[i]] = i + 1; // 转换为R的1-based索引
  }
  for (int i = 0; i < n; ++i) {
    double complement = target - nums[i];
    auto it = hash_map.find(complement);
    if (it != hash_map.end() && it->second != i + 1) {
      return IntegerVector::create(i + 1, it->second);
    }
  }
  return IntegerVector::create();
}
')

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