广州网站设计制作报价,wordpress备案显示,wordpress问答系统,网站开发竞品分析文章目录 题目描述与示例题目描述输入输出示例一输入输出说明 解题思路代码解法一pythonjavacpp 解法二pythonjavacpp 时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
给定一个整数数组nums#xff0c;请你在该数组中找出两个数#xff0c… 文章目录 题目描述与示例题目描述输入输出示例一输入输出说明 解题思路代码解法一pythonjavacpp 解法二pythonjavacpp 时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
给定一个整数数组nums请你在该数组中找出两个数使得这两个数的和的绝对值abs(nums[x] nums[y])为最小值并按从小到大返回这两个数以及它们和的绝对值。每种输入只会对应一个答案。数组中同一个元素不能使用两遍。
输入
一个通过空格分割的整数序列字符串最多1000个整数且整数数值范围是[-65535,65535]
输出
两个数以及两数之和绝对值
示例一
输入
-1 -3 7 5 11 15输出
-3 5 2说明
因为abs(nums[0]nums[2]) abs(-35) 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 - 1elif sum2 0:left 1else:break如果没有想到上述方法在选择left和right移动哪一个的问题上我们也可以直接考虑移动后的结果。当
abs(lst[left1] lst[right]) abs(lst[left] lst[right-1])即left右移后两数和的绝对值小于right左移的结果那么我们令left右移。abs(lst[left1] 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[left1] lst[right]) abs(lst[left] lst[right-1]):left 1else: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-1while left right:# 计算left和right所指两个元素的和sum2 lst[left] lst[right]# 如果两数和的绝对值小于之前记录的最小两数和的绝对值if abs(sum2) ans[2]:# 更新答案变量ansans [lst[left], lst[right], abs(sum2)]# 两数和大于0right左移if sum2 0:right - 1# 两数和小于0left右移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();ListInteger 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();ListInteger 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 algorithmusing namespace std;int main() {vectorint 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();vectorint 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;
}解法二
直接考虑移动哪一个指针能使两数和的绝对值更小。
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-1while left right:# 如果当前两数和绝对值小于当前记录的最小值则更新答案if abs(lst[left] lst[right]) ans[2]:ans [lst[left], lst[right], abs(sum2)]# left和right移动哪个能使得两数和绝对值更小则移动哪一个if abs(lst[left1] lst[right]) abs(lst[left] lst[right-1]):left 1else: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 );}}
}cpp
#include iostream
#include sstream
#include algorithm
#include vectorusing namespace std;int main() {string input;getline(cin, input);stringstream ss(input);vectorint lst;int num;while (ss num) {lst.push_back(num);}sort(lst.begin(), lst.end());int n lst.size();vectorint 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;
}时空复杂度
时间复杂度O(NlogN)。主要为排序的时间复杂度。
空间复杂度O(1)。忽略排序所需要的栈空间仅需要用到若干常数变量。 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
