41 和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得它们的和正好是S。如果有多对数字的和等于S，输出两个数的乘积最小的。

解题思路

核心思想：双指针，一个指向最左边，一个指向最右边。

关键步骤：

1. 左指针left从0开始，右指针right从len-1开始
2. 计算sum = nums[left] + nums[right]
3. 如果sum == S，记录结果，继续寻找（找乘积更小的）
4. 如果sum < S，left++（需要更大的数）
5. 如果sum > S，right--（需要更小的数）

时间复杂度：O(n) 空间复杂度：O(1)

Python 实现

def find_numbers_with_sum(nums, target):
    """
    在排序数组中找两个数，和为target

    Args:
        nums: 递增排序数组
        target: 目标和

    Returns:
        tuple: 两个数字，没有返回()
    """
    if not nums or len(nums) < 2:
        return ()

    left, right = 0, len(nums) - 1
    result = None

    while left < right:
        current_sum = nums[left] + nums[right]

        if current_sum == target:
            # 记录结果
            if result is None or nums[left] * nums[right] < result[0] * result[1]:
                result = (nums[left], nums[right])
            left += 1
            right -= 1
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return result if result else ()


# 测试代码
if __name__ == "__main__":
    test_cases = [
        ([1, 2, 3, 4, 5, 6, 7, 8], 9),
        ([1, 2, 3, 4, 5], 6),
        ([1, 2, 3, 4, 5], 10),
    ]

    for nums, target in test_cases:
        result = find_numbers_with_sum(nums, target)
        print(f"{nums}中和为{target}的两个数: {result}")

# 输出:
# [1, 2, 3, 4, 5, 6, 7, 8]中和为9的两个数: (1, 8)
# [1, 2, 3, 4, 5]中和为6的两个数: (1, 5)
# [1, 2, 3, 4, 5]中和为10的两个数: ()

图解

示例: [1,2,3,4,5,6,7,8], target=9

双指针过程:
left=0, right=7, sum=1+8=9, 记录(1,8), product=8
left=1, right=6, sum=2+7=9, 记录(2,7), product=14 (>8, 不更新)
left=2, right=5, sum=3+6=9, 记录(3,6), product=18 (>8, 不更新)
left=3, right=4, sum=4+5=9, 记录(4,5), product=20 (>8, 不更新)
left=4, right=3, left>=right, 结束

最终结果: (1, 8)

原理:
- 乘积最小的数对距离最远
- 因为数组是递增的，距离越远乘积越小
- 所以找到的第一对就是乘积最小的