当前位置: 代码迷 >> 综合 >> 1099 小于 K 的两数之和
  详细解决方案

1099 小于 K 的两数之和

热度:11   发布时间:2024-01-30 07:07:18.0

题目描述:
给你一个整数数组 A 和一个整数 K,请在该数组中找出两个元素,使它们的和小于 K 但尽可能地接近 K,返回这两个元素的和。
如不存在这样的两个元素,请返回 -1。

示例 1:
输入:A = [34,23,1,24,75,33,54,8], K = 60
输出:58
解释:
34 和 24 相加得到 58,58 小于 60,满足题意。

示例 2:
输入:A = [10,20,30], K = 15
输出:-1
解释:
我们无法找到和小于 15 的两个元素。

提示:
1 <= A.length <= 100
1 <= A[i] <= 1000
1 <= K <= 2000

方法1:双指针
主要思路:
(1)首先将输入的数组进行排序;
(2)对排序后的数组使用双指针分别指向头尾,逐渐更新两个数之和,并在这个过程中保存和小于目标值的最大值;

class Solution {
public:int twoSumLessThanK(vector<int>& A, int K) {if(A.size()<2)return -1;sort(A.begin(),A.end());//对原数组进行排序//定义双指针int left=0;int right=A.size()-1;//保存过程中的最大值int min_K=INT_MIN;//更新范围while(left<right){if(A[left]+A[right]<K){//若和小于目标值,则更新min_K,同时更新左指针min_K=max(min_K,A[left]+A[right]);++left;}else{--right;//更新右指针}}return min_K==INT_MIN?-1:min_K;//根据值是否更新,返回结果}
};