如何高效计算两字典匹配键下符合条件的日期间隔总天数？

核心思路 #

先提取两个字典的共同键，对每个共同键对应的日期列表：

1. 将日期字符串转换为可计算的date对象（避免字符串操作的低效）
2. 对两个日期列表分别按升序排序
3. 使用双指针法遍历两个排序后的列表，贪心匹配符合条件的日期对（dict1的日期 > dict2的日期），累加天数差

这种方法的时间复杂度为O(K*(N log N + M log M + N + M))，其中K是共同键的数量，N、M分别是单个键下dict1和dict2的日期列表长度，相比暴力遍历所有日期对的O(KNM)，在列表较长时效率提升明显。

代码实现 #

from datetime import datetime

def str_to_date(date_str):
    # 固定格式的日期字符串转date对象，比通用解析库更高效
    return datetime.strptime(date_str, '%Y-%m-%d').date()

def calculate_total_days(dict1, dict2):
    total_days = 0
    # 获取两个字典的共同键
    common_keys = dict1.keys() & dict2.keys()
    
    for key in common_keys:
        # 转换并排序日期列表
        d1_dates = sorted(str_to_date(d) for d in dict1[key])
        d2_dates = sorted(str_to_date(d) for d in dict2[key])
        
        i = j = 0
        len1, len2 = len(d1_dates), len(d2_dates)
        
        while i < len1 and j < len2:
            d1 = d1_dates[i]
            d2 = d2_dates[j]
            
            if d1 > d2:
                # 计算天数差并累加
                total_days += (d1 - d2).days
                # 匹配下一组日期对
                i += 1
                j += 1
            else:
                # 当前dict1日期不够大，跳过
                i += 1
    return total_days

# 测试示例
if __name__ == "__main__":
    # 示例1
    dict1_a = {'a': ['2022-07-27']}
    dict2_a = {'a': ['2022-07-21']}
    print(calculate_total_days(dict1_a, dict2_a))  # 输出6
    
    # 示例2
    dict1_b = {'b': ['2021-09-14', '2022-08-08']}
    dict2_b = {'b': ['2022-08-01']}
    print(calculate_total_days(dict1_b, dict2_b))  # 输出7
    
    # 示例3
    dict1_c = {'c': ['2021-07-28', '2022-07-07', '2022-09-17']}
    dict2_c = {'c': ['2022-05-01', '2022-07-27']}
    print(calculate_total_days(dict1_c, dict2_c))  # 输出119

关键细节说明 #

• 日期转换：使用datetime.strptime处理固定格式的日期字符串，比通用解析库更高效；如果日期格式不固定，可以改用dateutil.parser.parse（需提前安装python-dateutil）。
• 排序的必要性：双指针法依赖有序列表，才能保证贪心匹配的正确性和高效性。
• 双指针逻辑：每次找到符合条件的日期对后，同时移动两个指针，确保每个日期只被匹配一次，避免重复计算，完全符合你给出的示例规则。

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