如何针对double类型数组求解两数之和问题？

Great question! When moving from integer arrays to double-precision floating point arrays for the two-sum problem, the biggest shift is accounting for floating point precision errors—mathematically equal values might not match exactly in binary storage. Here's how to adapt the two standard solutions to handle this:

1. Hash Map Approach (Adapted for Precision) #

The integer version relies on exact equality checks for complements, but for doubles, we need to check if values are close enough instead of exactly the same.

Steps: #

• Pick a small epsilon value (like 1e-9) to define how close two doubles need to be to count as equal.
• Iterate through the array, and for each element nums[i]:
  • Calculate the complement: complement = target - nums[i]
  • Check if the hash map contains any value within epsilon of the complement
  • If found, return the stored index and current index i
  • If not, store the current value and its index in the map

Example Code (Python): #

def two_sum_double(nums, target, epsilon=1e-9):
    num_map = {}
    for idx, num in enumerate(nums):
        complement = target - num
        # Check for near-equality with stored values
        for stored_num, stored_idx in num_map.items():
            if abs(stored_num - complement) < epsilon:
                return [stored_idx, idx]
        num_map[num] = idx
    return []

Optimization Tip: To avoid the nested loop, round values to a fixed number of decimal places (matching your epsilon) before storing them. This lets you use exact equality checks:

def two_sum_double_optimized(nums, target, precision=9):
    num_map = {}
    for idx, num in enumerate(nums):
        rounded_num = round(num, precision)
        complement = round(target - num, precision)
        if complement in num_map:
            return [num_map[complement], idx]
        num_map[rounded_num] = idx
    return []

2. Two-Pointer Approach (With Precision Checks) #

Sorting and two pointers works for doubles too, but we need to track original indices and use epsilon for sum comparisons.

Steps: #

• Create a list of tuples pairing each value with its original index
• Sort this list by the value field
• Initialize left at the start and right at the end of the sorted list
• Loop while left < right:
  • Calculate the current sum of the two pointer values
  • If the sum is within epsilon of the target, return the original indices
  • If the sum is too small, move the left pointer right to increase the sum
  • If the sum is too large, move the right pointer left to decrease the sum

Example Code (Python): #

def two_sum_double_two_pointers(nums, target, epsilon=1e-9):
    # Preserve original indices while sorting
    sorted_nums = sorted([(num, idx) for idx, num in enumerate(nums)], key=lambda x: x[0])
    left = 0
    right = len(sorted_nums) - 1
    while left < right:
        current_sum = sorted_nums[left][0] + sorted_nums[right][0]
        if abs(current_sum - target) < epsilon:
            return [sorted_nums[left][1], sorted_nums[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

Key Notes #

• Epsilon Selection: Choose an epsilon that matches your data's precision. 1e-9 works for most standard double use cases, but adjust if you're dealing with very large or very small values.
• Performance: The optimized hash map approach runs in O(n) average time, while the two-pointer approach has O(n log n) time due to sorting.
• Duplicates: Both methods handle duplicate values correctly, as long as you don't overwrite earlier indices in the hash map (the check happens before insertion, so the first occurrence is preserved).

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