題目描述與示例

題目描述

給定一個(gè)整數(shù)數(shù)組nums，請(qǐng)你在該數(shù)組中找出兩個(gè)數(shù)，使得這兩個(gè)數(shù)的和的絕對(duì)值abs(nums[x] + nums[y])為最小值并按從小到大返回這兩個(gè)數(shù)以及它們和的絕對(duì)值。每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。數(shù)組中同一個(gè)元素不能使用兩遍。

輸入

一個(gè)通過(guò)空格分割的整數(shù)序列字符串，最多1000個(gè)整數(shù)，且整數(shù)數(shù)值范圍是[-65535,65535]

輸出

兩個(gè)數(shù)以及兩數(shù)之和絕對(duì)值

示例一

輸入

-1 -3 7 5 11 15

輸出

-3 5 2

說(shuō)明

因?yàn)?code>abs(nums[0]+nums[2]) = abs(-3+5) = 2在所有數(shù)對(duì)中最小，所以返回-3 5 2

解題思路

注意，本題和LC167. 兩數(shù)之和 II - 輸入有序數(shù)組解題方法非常類(lèi)似。但在判斷指針移動(dòng)的條件上，稍微有些不同。

要用上相向雙指針，首先要對(duì)lst數(shù)組進(jìn)行排序。

兩個(gè)數(shù)的和的絕對(duì)值越小，說(shuō)明這兩個(gè)數(shù)的和越接近于0。所以這道題可以換一種問(wèn)法，找到兩個(gè)數(shù)使得它們的和盡可能地接近0。我們可以使用相向雙指針left和right指向一小一大兩個(gè)數(shù)，當(dāng)

• lst[left] + lst[right] > 0時(shí)，如果令left右移，兩數(shù)和會(huì)進(jìn)一步增大，距離0更遠(yuǎn)，因此需要令right左移。
• lst[left] + lst[right] < 0時(shí)，如果令right左移，兩數(shù)和會(huì)進(jìn)一步減小，距離0更遠(yuǎn)，因此需要令left右移。
• lst[left] + lst[right] == 0時(shí)，兩數(shù)和的絕對(duì)值已經(jīng)達(dá)到最小，可以直接退出循環(huán)。

另外，對(duì)于每對(duì)兩數(shù)和sum2 = lst[left] + lst[right]，我們都應(yīng)該令其絕對(duì)值與之前的得到最小兩數(shù)和絕對(duì)值進(jìn)行比較并更新。上述思路整理為代碼即：

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

如果沒(méi)有想到上述方法，在選擇left和right移動(dòng)哪一個(gè)的問(wèn)題上，我們也可以直接考慮移動(dòng)后的結(jié)果。當(dāng)

• abs(lst[left+1] + lst[right]) < abs(lst[left] + lst[right-1])，即left右移后兩數(shù)和的絕對(duì)值小于right左移的結(jié)果，那么我們令left右移。
• abs(lst[left+1] + lst[right]) >= abs(lst[left] + lst[right-1])，即left右移后兩數(shù)和的絕對(duì)值大于等于right左移的結(jié)果，那么我們令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 += 1else:right -= 1

代碼

解法一

將題目轉(zhuǎn)化為考慮最接近target = 0的兩數(shù)和

python

# 題目：2023Q1A-兩數(shù)之和絕對(duì)值最小
# 分值：100
# 作者：許老師-閉著眼睛學(xué)數(shù)理化
# 算法：相向雙指針
# 代碼看不懂的地方，請(qǐng)直接在群上提問(wèn)lst = list(map(int, input().split()))
lst.sort()
n = len(lst)# 答案變量ans為一個(gè)三元列表，分別為兩個(gè)數(shù)以及兩數(shù)和的絕對(duì)值
ans = [lst[0], lst[-1], abs(lst[0]+lst[-1])]left, right = 0, n-1while left < right:# 計(jì)算left和right所指兩個(gè)元素的和sum2 = lst[left] + lst[right]# 如果兩數(shù)和的絕對(duì)值小于之前記錄的最小兩數(shù)和的絕對(duì)值if abs(sum2) < ans[2]:# 更新答案變量ansans = [lst[left], lst[right], abs(sum2)]# 兩數(shù)和大于0，right左移if sum2 > 0:right -= 1# 兩數(shù)和小于0，left右移elif sum2 < 0:left += 1# 兩數(shù)和等于0，退出循環(huán)else:break# 用map把a(bǔ)ns中的所有int轉(zhuǎn)為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();}
}

cpp

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {vector<int> lst;string input;getline(cin, input);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;
}

解法二

直接考慮移動(dòng)哪一個(gè)指針，能使兩數(shù)和的絕對(duì)值更小。

python

# 題目：2023Q1A-兩數(shù)之和絕對(duì)值最小
# 分值：100
# 作者：許老師-閉著眼睛學(xué)數(shù)理化
# 算法：相向雙指針
# 代碼看不懂的地方，請(qǐng)直接在群上提問(wèn)lst = list(map(int, input().split()))
lst.sort()
n = len(lst)# 答案變量ans為一個(gè)三元列表，分別為兩個(gè)數(shù)以及兩數(shù)和的絕對(duì)值
ans = [lst[0], lst[-1], abs(lst[0]+lst[-1])]left, right = 0, n-1while left < right:# 如果當(dāng)前兩數(shù)和絕對(duì)值小于當(dāng)前記錄的最小值，則更新答案if abs(lst[left] + lst[right]) < ans[2]:ans = [lst[left], lst[right], abs(sum2)]# left和right移動(dòng)哪個(gè)能使得兩數(shù)和絕對(duì)值更小，則移動(dòng)哪一個(gè)if abs(lst[left+1] + lst[right]) < abs(lst[left] + lst[right-1]):left += 1else:right -= 1# 用map把a(bǔ)ns中的所有int轉(zhuǎn)為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為一個(gè)三元數(shù)組，分別為兩個(gè)數(shù)以及兩數(shù)和的絕對(duì)值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) {// 如果當(dāng)前兩數(shù)和絕對(duì)值小于當(dāng)前記錄的最小值，則更新答案if (Math.abs(lst[left] + lst[right]) < ans[2]) {ans = new int[]{lst[left], lst[right], Math.abs(lst[left] + lst[right])};}// left和right移動(dòng)哪個(gè)能使得兩數(shù)和絕對(duì)值更小，則移動(dòng)哪一個(gè)if (Math.abs(lst[left + 1] + lst[right]) < Math.abs(lst[left] + lst[right - 1])) {left++;} else {right--;}}// 輸出結(jié)果for (int num : ans) {System.out.print(num + " ");}}
}

cpp

#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();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;
}

時(shí)空復(fù)雜度

時(shí)間復(fù)雜度：O(NlogN)。主要為排序的時(shí)間復(fù)雜度。

空間復(fù)雜度：O(1)。忽略排序所需要的棧空間，僅需要用到若干常數(shù)變量。

---

華為OD算法/大廠面試高頻題算法練習(xí)沖刺訓(xùn)練

• 華為OD算法/大廠面試高頻題算法沖刺訓(xùn)練目前開(kāi)始常態(tài)化報(bào)名！目前已服務(wù)100+同學(xué)成功上岸！

• 課程講師為全網(wǎng)50w+粉絲編程博主@吳師兄學(xué)算法 以及小紅書(shū)頭部編程博主@閉著眼睛學(xué)數(shù)理化

• 每期人數(shù)維持在20人內(nèi)，保證能夠最大限度地滿足到每一個(gè)同學(xué)的需求，達(dá)到和1v1同樣的學(xué)習(xí)效果！

• 60+天陪伴式學(xué)習(xí)，40+直播課時(shí)，300+動(dòng)畫(huà)圖解視頻，300+LeetCode經(jīng)典題，200+華為OD真題/大廠真題，還有簡(jiǎn)歷修改、模擬面試、專(zhuān)屬HR對(duì)接將為你解鎖

• 可上全網(wǎng)獨(dú)家的歐弟OJ系統(tǒng)練習(xí)華子OD、大廠真題

• 可查看鏈接 大廠真題匯總 & OD真題匯總(持續(xù)更新)

• 綠色聊天軟件戳 od1336了解更多