题目描述与示例

题目描述

给定一个整数数组nums，请你在该数组中找出两个数，使得这两个数的和的绝对值abs(nums[x] + nums[y])为最小值并按从小到大返回这两个数以及它们和的绝对值。每种输入只会对应一个答案。数组中同一个元素不能使用两遍。

输入

一个通过空格分割的整数序列字符串，最多1000个整数，且整数数值范围是[-65535,65535]

输出

两个数以及两数之和绝对值

示例一

输入

-1 -3 7 5 11 15

输出

-3 5 2

说明

因为abs(nums[0]+nums[2]) = abs(-3+5) = 2在所有数对中最小，所以返回-3 5 2

解题思路

注意，本题和LC167. 两数之和 II – 输入有序数组解题方法非常类似。但在判断指针移动的条件上，稍微有些不同。

要用上相向双指针，首先要对lst数组进行排序。

两个数的和的绝对值越小，说明这两个数的和越接近于0。所以这道题可以换一种问法，找到两个数使得它们的和尽可能地接近0。我们可以使用相向双指针left和right指向一小一大两个数，当

  • lst[left] + lst[right] > 0时，如果令left右移，两数和会进一步增大，距离0更远，因此需要令right左移。
  • lst[left] + lst[right] < 0时，如果令right左移，两数和会进一步减小，距离0更远，因此需要令left右移。
  • lst[left] + lst[right] == 0时，两数和的绝对值已经达到最小，可以直接退出循环。

另外，对于每对两数和sum2 = lst[left] + lst[right]，我们都应该令其绝对值与之前的得到最小两数和绝对值进行比较并更新。上述思路整理为代码即：

while left < right:
    sum2 = lst[left] + lst[right]
    if abs(sum2) < ans[2]:
        ans = [lst[left], lst[right], abs(sum2)]
    if sum2 > 0:
        right -= 1
    elif sum2 < 0:
        left += 1
    else:
        break

如果没有想到上述方法，在选择left和right移动哪一个的问题上，我们也可以直接考虑移动后的结果。当

  • abs(lst[left+1] + lst[right]) < abs(lst[left] + lst[right-1])，即left右移后两数和的绝对值小于right左移的结果，那么我们令left右移。
  • abs(lst[left+1] + lst[right]) >= abs(lst[left] + lst[right-1])，即left右移后两数和的绝对值大于等于right左移的结果，那么我们令right左移。

上述思路整理为代码即：

while left < right:
    if abs(lst[left] + lst[right]) < ans[2]:
        ans = [lst[left], lst[right], abs(sum2)]
    if abs(lst[left+1] + lst[right]) < abs(lst[left] + lst[right-1]):
        left += 1
    else:
        right -= 1

代码

解法一

将题目转化为考虑最接近target = 0的两数和

Python

# 题目：2023Q1A-两数之和绝对值最小
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：相向双指针
# 代码看不懂的地方，请直接在群上提问

lst = list(map(int, input().split()))
lst.sort()
n = len(lst)

# 答案变量ans为一个三元列表，分别为两个数以及两数和的绝对值
ans = [lst[0], lst[-1], abs(lst[0]+lst[-1])]

left, right = 0, n-1

while left < right:
    # 计算left和right所指两个元素的和
    sum2 = lst[left] + lst[right]
    # 如果两数和的绝对值小于之前记录的最小两数和的绝对值
    if abs(sum2) < ans[2]:
        # 更新答案变量ans
        ans = [lst[left], lst[right], abs(sum2)]
    # 两数和大于0，right左移
    if sum2 > 0:
        right -= 1
    # 两数和小于0，left右移
    elif sum2 < 0:
        left += 1
    # 两数和等于0，退出循环
    else:
        break

# 用map把ans中的所有int转为str，合并后输出
print(" ".join(map(str, ans)))

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        List<Integer> lst = new ArrayList<>();

        while (input.contains(" ")) {
            int pos = input.indexOf(' ');
            lst.add(Integer.parseInt(input.substring(0, pos)));
            input = input.substring(pos + 1);
        }
        lst.add(Integer.parseInt(input));

        lst.sort(null);
        int n = lst.size();

        List<Integer> ans = Arrays.asList(lst.get(0), lst.get(n - 1), Math.abs(lst.get(0) + lst.get(n - 1)));

        int left = 0;
        int right = n - 1;

        while (left < right) {
            int sum2 = lst.get(left) + lst.get(right);
            if (Math.abs(sum2) < ans.get(2)) {
                ans = Arrays.asList(lst.get(left), lst.get(right), Math.abs(sum2));
            }
            if (sum2 > 0) {
                right--;
            } else if (sum2 < 0) {
                left++;
            } else {
                break;
            }
        }

        for (int num : ans) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

C++

“`C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
vector<int> lst;
string input;
getline(cin, input);

<pre><code>size_t pos = 0;
while ((pos = input.find(' ')) != string::npos) {
lst.push_back(stoi(input.substr(0, pos)));
input.erase(0, pos + 1);
}
lst.push_back(stoi(input));

sort(lst.begin(), lst.end());
int n = lst.size();

vector<int> ans = {lst[0], lst[n – 1], abs(lst[0] + lst[n – 1])};

int left = 0;
int right = n – 1;

while (left < right) {
int sum2 = lst[left] + lst[right];
if (abs(sum2) < ans[2]) {
ans = {lst[left], lst[right], abs(sum2)};
}
if (sum2 > 0) {
right–;
} else if (sum2 < 0) {
left++;
} else {
break;
}
}

for (int num : ans) {
cout << num << " ";
}
cout << endl;

return 0;
</code></pre>

}

<pre><code class="">## 解法二

直接考虑移动哪一个指针，能使两数和的绝对值更小。

### Python

“`Python
# 题目：2023Q1A-两数之和绝对值最小
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：相向双指针
# 代码看不懂的地方，请直接在群上提问

lst = list(map(int, input().split()))
lst.sort()
n = len(lst)

# 答案变量ans为一个三元列表，分别为两个数以及两数和的绝对值
ans = [lst[0], lst[-1], abs(lst[0]+lst[-1])]

left, right = 0, n-1

while left < right:
# 如果当前两数和绝对值小于当前记录的最小值，则更新答案
if abs(lst[left] + lst[right]) < ans[2]:
ans = [lst[left], lst[right], abs(sum2)]
# left和right移动哪个能使得两数和绝对值更小，则移动哪一个
if abs(lst[left+1] + lst[right]) < abs(lst[left] + lst[right-1]):
left += 1
else:
right -= 1

# 用map把ans中的所有int转为str，合并后输出
print(” “.join(map(str, ans)))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] tokens = input.split("\\s+");
        int[] lst = new int[tokens.length];
        for (int i = 0; i < tokens.length; i++) {
            lst[i] = Integer.parseInt(tokens[i]);
        }
        Arrays.sort(lst);
        int n = lst.length;

        // 答案变量ans为一个三元数组，分别为两个数以及两数和的绝对值
        int[] ans = new int[]{lst[0], lst[n - 1], Math.abs(lst[0] + lst[n - 1])};

        int left = 0;
        int right = n - 1;

        while (left < right) {
            // 如果当前两数和绝对值小于当前记录的最小值，则更新答案
            if (Math.abs(lst[left] + lst[right]) < ans[2]) {
                ans = new int[]{lst[left], lst[right], Math.abs(lst[left] + lst[right])};
            }
            // left和right移动哪个能使得两数和绝对值更小，则移动哪一个
            if (Math.abs(lst[left + 1] + lst[right]) < Math.abs(lst[left] + lst[right - 1])) {
                left++;
            } else {
                right--;
            }
        }

        // 输出结果
        for (int num : ans) {
            System.out.print(num + " ");
        }
    }
}

C++

“`C++
#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
string input;
getline(cin, input);
stringstream ss(input);
vector<int> lst;
int num;
while (ss >> num) {
lst.push_back(num);
}
sort(lst.begin(), lst.end());
int n = lst.size();

<pre><code>vector<int> ans = {lst[0], lst[n – 1], abs(lst[0] + lst[n – 1])};

int left = 0;
int right = n – 1;

while (left < right) {
if (abs(lst[left] + lst[right]) < ans[2]) {
ans = {lst[left], lst[right], abs(lst[left] + lst[right])};
}
if (abs(lst[left + 1] + lst[right]) < abs(lst[left] + lst[right – 1])) {
left++;
} else {
right–;
}
}

for (int num : ans) {
cout << num << " ";
}
cout << endl;

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(NlogN)。主要为排序的时间复杂度。

空间复杂度：O(1)。忽略排序所需要的栈空间，仅需要用到若干常数变量。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）

上一篇 【双指针】2023C-跳房子II
下一篇 【双指针】2023B-太阳能航天器

相关文章