如何在不使用双重循环的情况下计算数组中所有日期对的差值

如果你的需求是计算所有两两日期差值的总和，完全可以避开O(n²)的双重循环，用「排序+前缀和」的方法将时间复杂度降到O(n log n)，数据量越大，效率提升越明显。以下是具体实现步骤：

步骤1：将日期字符串转换为数值化天数 #

先把每个日期字符串转换成可计算的整数（比如Python中datetime.date.toordinal()可以直接返回从公元1年1月1日开始的天数），让日期差值变成整数运算，方便后续处理。

示例代码：

from datetime import datetime

def str_to_days(date_str):
    # 适配你的日期格式：dd/mm/yyyy
    dt = datetime.strptime(date_str, "%d/%m/%Y").date()
    return dt.toordinal()

# 示例数组
arr = ['01/01/2020', '15/11/2021', '05/07/2018', '01/03/2020', '10/10/2022', '07/02/2015']
days_arr = [str_to_days(date) for date in arr]

步骤2：对天数数组排序 #

排序的时间复杂度是O(n log n)，这是整个流程中耗时最长的步骤，但远优于O(n²)。排序后可以利用数学规律批量计算差值总和，无需两两遍历。

days_arr.sort()

步骤3：用前缀和计算总差值 #

假设排序后的数组为d[0], d[1], ..., d[n-1]，对于每个元素d[i]（i从1开始），它与前面所有i个元素的差值总和为：d[i] * i - sum(d[0..i-1])。我们用前缀和数组快速计算sum(d[0..i-1])，避免重复求和。

示例代码：

total_diff = 0
prefix_sum = 0  # 前缀和，初始为0（空数组的和）

for i in range(len(days_arr)):
    if i == 0:
        prefix_sum = days_arr[i]
        continue
    # 当前元素与前面i个元素的差值总和
    total_diff += days_arr[i] * i - prefix_sum
    # 更新前缀和，加入当前元素
    prefix_sum += days_arr[i]

print(f"所有日期对的差值总和：{total_diff} 天")

关键原理说明 #

排序后，每个元素d[i]比前面所有i个元素都大，因此它与前面每个元素的差值都是d[i]-d[j]（j < i）。把这些差值累加，等价于d[i]被加i次，前面i个元素的和被减1次。通过前缀和记录前面元素的累加和，就能在O(1)时间内算出每个元素对应的差值贡献，最终总时间复杂度为O(n log n)。

如果你的需求是获取每一对日期的具体差值，那么无法避免O(n²)的时间复杂度——因为总共有n*(n-1)/2个日期对，必须遍历所有对才能输出结果。但此时可以先排序再遍历，让差值计算更直观（无需判断大小），但时间复杂度仍为O(n²)。

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