刷题笔记合集🔗

问题描述

小兰在研究数列时发现了一个有趣的问题。给定一个从小到大的有序整数序列（包含正数和负数），需要在序列中找出两个不同的数，使它们的和的绝对值最小。

例如序列 [-3, -1, 5, 7, 11, 15] 中：

• |-3 + 5| = 2 是所有可能组合中的最小值
• 每个数字只能使用一次

输入格式

输入一行，包含一个有序整数序列，数字之间用空格分隔。

输出格式

输出一个整数，表示找到的两个数之和的绝对值的最小值。

样例输入1

-3 -1 5 7 11 15

样例输出1

2

样例解释

|-3 + 5| = 2 是所有可能组合中的最小值。

数据范围

• 序列长度不超过1000
• 序列中的整数范围在[-65535, 65535]之间
• 序列已按从小到大排序
• 序列中的每个数字只能使用一次

题解

这道题可以有两种解法：

1. 暴力解法

• 双重循环遍历所有可能的组合
• 记录所有组合中和的绝对值的最小值
• 时间复杂度：O(n²)

2. 二分查找优化

• 利用序列有序的特点
• 对于每个负数，二分查找最接近其相反数的正数
• 时间复杂度：O(nlogn)

参考代码

def solve(nums):
    """
    nums: 输入的有序数组
    return: 两数之和绝对值的最小值
    """
    min_sum = float('inf')
    n = len(nums)
    
    # 找到第一个非负数的位置
    pos = 0
    while pos < n and nums[pos] < 0:
        pos += 1
    
    # 检查相邻的负数对
    for i in range(pos - 1):
        min_sum = min(min_sum, abs(nums[i] + nums[i + 1]))
    
    # 检查相邻的正数对
    for i in range(pos, n - 1):
        min_sum = min(min_sum, abs(nums[i] + nums[i + 1]))
    
    # 检查跨越0的数对
    for i in range(pos):
        left, right = pos, n - 1
        target = -nums[i]
        
        while left <= right:
            mid = (left + right) // 2
            curr_sum = abs(nums[i] + nums[mid])
            min_sum = min(min_sum, curr_sum)
            
            if nums[mid] == target:
                return 0
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
    
    return min_sum

# 读取输入
nums = list(map(int, input().split()))
# 输出结果
print(solve(nums))

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<int>& nums) {
        int min_sum = INT_MAX;
        int n = nums.size();
        
        // 找到第一个非负数的位置
        int pos = 0;
        while (pos < n && nums[pos] < 0) pos++;
        
        // 检查相邻的负数对
        for (int