刷题笔记合集🔗

最小绝对值之和

问题描述

给定一个从小到大的有序整数序列（存在正整数和负整数）数组 ，请你在该数组中找出两个数，其和的绝对值 为最小值，并返回这个绝对值。

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

输入格式

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

输出格式

两数之和绝对值最小值。

样例输入

-3 -1 5 7 11 15

样例输出

2

数据范围

• 整数序列长度
• 整数取值范围
• 整数序列已按从小到大排序

题解

这道题目要求我们找出有序数组中两个数，使得它们的和的绝对值最小。乍一看似乎需要尝试所有可能的组合，但我们可以利用数组已经排序的特性来优化解法。

思路分析

首先，我们可以观察到：

1. 如果数组全为正数，那么最小的绝对值和是最小的两个数之和
2. 如果数组全为负数，那么最小的绝对值和是最大的两个负数之和的绝对值
3. 如果数组既有正数也有负数，那么最小的绝对值和可能来自：
   • 两个负数之和的绝对值
   • 两个正数之和
   • 一个负数和一个正数之和的绝对值（这种情况最可能得到接近0的结果）

对于第三种情况，我们希望找到和为0或接近0的两个数。因为数组已排序，我们可以使用二分查找来加速这个过程。

实现方法

我们的解决方案是：

1. 找到数组中第一个非负数的位置（通过二分查找）
2. 基于这个位置，我们可以将数组分为负数部分和非负数部分
3. 考虑几种可能的组合：
   • 负数部分的最后两个数（它们是最大的负数）
   • 非负数部分的前两个数（它们是最小的非负数）
   • 负数部分的每个数与非负数部分中最接近其相反数的数组合

时间复杂度分析

使用二分查找优化后，算法的时间复杂度为 ，这对于最多1000个整数的输入规模是足够高效的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

def min_abs_sum(nums):
    # 二分查找找到第一个非负数的位置
    def binary_find(arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] < target:
                left = mid + 1
            elif arr[mid] > target:
                right = mid - 1
            else:
                return mid
        return left
    
    # 查找第一个非负数的索引
    idx = binary_find(nums, 0)
    
    # 如果全是正数或0（第一个元素就是非负数）
    if idx == 0:
        return nums[0] + nums[1]
    
    # 如果全是负数（没有找到非负数）
    n = len(nums)
    if idx == n:
        return abs(nums[n-2] + nums[n-1])
    
    # 有正有负的情况
    min_val = float('inf')
    
    # 检查负数部分最大的两个数
    if idx >= 2:
        min_val = min(min_val, abs(nums[idx-2] + nums[idx-1]))
    
    # 检查非负数部分最小的两个数
    if idx < n-1:
        min_val = min(min_val, nums[idx] + nums[idx+1])
    
    # 检查每个负数和非负数部分最接近其相反数的数
    pos_nums = nums[idx:]
    for i in range(idx):
        # 找到最接近-nums[i]的位置
        j = binary_find(pos_nums, -nums[i])
        
        if j < len(pos_nums):
            min_val = min(min_val, abs(nums[i] + pos_nums[j]))
        
        if j > 0:
            min_val = min(min_val, abs(nums[i] + pos_nums[j-1]))
    
    return min_val

# 读取输入
nums = list(map(int, input().split()))
print(min_abs_sum(nums))

• Cpp

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

int min_abs_sum(vector<int>& nums) {
    // 二分查找
    auto find_pos = [&](int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (ri