刷题笔记合集🔗

乱序整数序列两数之和绝对值最小

问题描述

小兰有一个随机的整数（可能存在正整数和负整数）数组 ，请你在该数组中找出两个数，其和的绝对值（）为最小值，并返回这个两个数（按从小到大返回）以及绝对值。

每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

输入格式

一个通过空格分割的有序整数序列字符串，最多 个整数，且整数数值范围是 。

输出格式

两数之和绝对值最小值，格式为：较小的数 较大的数 绝对值。

样例输入

-1 -3 7 5 11 15

样例输出

-3 5 2

数据范围

• 数组最多包含 个整数
• 整数数值范围是

题解

这道题目要求在数组中找出两个数，使得它们的和的绝对值最小，并按照从小到大的顺序输出这两个数以及它们和的绝对值。

思路分析

一种朴素的做法是穷举所有可能的数对，计算它们和的绝对值，找出最小值。由于数据规模不大（最多1000个整数），这种方法是可行的。

对于更优的解法，可以利用数组的有序性质，先排序，然后根据不同情况处理：

1. 如果数组全是非负数，最小绝对值和可能是最小的两个数之和
2. 如果数组全是负数，最小绝对值和可能是最大的两个数之和
3. 如果数组有正有负，最小绝对值和可能来自：
   • 负数部分最大的两个数之和
   • 正数部分最小的两个数之和
   • 一正一负且和接近零的两个数

优化解法的关键在于使用二分查找定位第一个非负数的位置，然后分情况考虑可能的最小绝对值。

时间复杂度分析

• 朴素解法：O(n²)，其中n是数组长度
• 优化解法：O(n log n)，主要是排序的时间复杂度

对于给定的数据范围（最多1000个整数），两种解法都可以通过，但优化解法在大规模数据下更具优势。

参考代码

• Python

import bisect

def check(min_val, ans, n1, n2):
    """比较和检查两数的函数，更新最小和结果
    
    Args:
        min_val: 当前最小和的绝对值
        ans: 当前结果字符串
        n1: 第一个数
        n2: 第二个数
    """
    sum_abs = abs(n1 + n2)
    if min_val > sum_abs:
        min_val = sum_abs
        # 确保较小的数在前
        sm = min(n1, n2)
        lg = max(n1, n2)
        # 更新结果为字符串：小数字 大数字 和的绝对值
        ans[0] = f"{sm} {lg} {sum_abs}"
    return min_val

def solve(nums):
    """解决函数：找到和绝对值最小的两个数
    
    Args:
        nums: 整数列表
        
    Returns:
        返回格式化的结果字符串
    """
    # 对数组进行排序
    nums.sort()
    
    # 找到第一个非负数的位置
    # bisect_left返回插入位置，即第一个不小于0的元素位置
    idx = bisect.bisect_left(nums, 0)
    n = len(nums)
    
    # 处理全是非负数的情况
    if idx == 0:
        sum_abs = nums[0] + nums[1]
        return f"{nums[0]} {nums[1]} {sum_abs}"
    
    # 处理全是负数的情况
    if idx >= n:
        sum_abs = abs(nums[-2] + nums[-1])
        return f"{nums[-2]} {nums[-1]} {sum_abs}"
    
    # 初始化最小值为最大整数，结果存储为列表以便在check函数中修改
    min_val = float('inf')
    ans = [""]
    
    # 检查负数部分的最后两个数（最大的两个负数）
    if idx >= 2:
        min_val = check(min_val, ans, nums[idx-2], nums[idx-1])
    
    # 检查非负数部分的前两个数（最小的两个非负数）
    if idx < n - 1:
        min_val = check(min_val, ans, nums[idx], nums[idx+1])
    
    # 提取所有非负数部分用于二分查找
    pos_nums = nums[idx:]
    
    # 检查正负数组合
    for i in range(idx):  # 遍历所有负数
        # 在非负数部分找最接近当前负数绝对值的数
        target = -nums[i]
        # 使用bisect_left找到插入位置
        pos = bisect.bisect_left(pos_nums, target)
        
        # 检查找到的位置是否在范围内
        if pos < len(pos_nums):
            min_val = check(min_val, ans, nums[i], pos_nums[pos])
        
        # 检查前一个位置是否在范围内
        if pos > 0:
            min_val = check(min_val, ans, nums[i], pos_nums[pos-1])
    
    return ans[0]

# 读取输入
line = input().strip()
# 将输入字符串转换为整数列表
nums = list(map(int, line.split()))
# 调用solve函数并输出结果
print(solve(nums))

• Cpp

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

// 比较和检查两数的函数
void check(int& min_val,