网站建设意见征求,虾子酱 wordpress,wordpress开玩笑 呵,怡梦姗网站做么文章目录1. 题目2. 解题2.1 暴力2.2 二分查找1. 题目
给你一个整数数组 A 和一个整数 K#xff0c;请在该数组中找出两个元素#xff0c;使它们的和小于 K 但尽可能地接近 K#xff0c;返回这两个元素的和。
如不存在这样的两个元素#xff0c;请返回 -1。
示例 1#…
文章目录1. 题目2. 解题2.1 暴力2.2 二分查找1. 题目
给你一个整数数组 A 和一个整数 K请在该数组中找出两个元素使它们的和小于 K 但尽可能地接近 K返回这两个元素的和。
如不存在这样的两个元素请返回 -1。
示例 1
输入A [34,23,1,24,75,33,54,8], K 60
输出58
解释
34 和 24 相加得到 5858 小于 60满足题意。示例 2
输入A [10,20,30], K 15
输出-1
解释
我们无法找到和小于 15 的两个元素。提示
1 A.length 100
1 A[i] 1000
1 K 2000来源力扣LeetCode 链接https://leetcode-cn.com/problems/two-sum-less-than-k 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 暴力
class Solution {
public:int twoSumLessThanK(vectorint A, int K) {int i, j, n A.size(), sum, mindiff INT_MAX;for(i 0; i n-1; i){for(j i 1; j n; j){if(A[i]A[j] K K-A[i]-A[j] mindiff){mindiff K-A[i]-A[j];sum A[i]A[j];}}}return mindiffINT_MAX ? -1 : sum;}
};4 ms 9.2 MB
2.2 二分查找
排序固定一个数二分查找另一个数
class Solution {
public:int twoSumLessThanK(vectorint A, int K) {sort(A.begin(), A.end());int sum, mindiff INT_MAX, l, r, mid, t;for(int i 0; i A.size(); i){l 0, r A.size()-1;t K-A[i];//找到小于t的最大数while(l r){mid l((r-l)1);if(A[mid] t)r mid-1;else{if(midA.size()-1 || A[mid1] t){ //找到了 if(mid ! i K-A[mid]-A[i] mindiff){ //不是同一个数且更接近mindiff K-A[mid]-A[i];sum A[mid]A[i];}break;}elsel mid1;}}}return mindiffINT_MAX ? -1 : sum;}
};4 ms 9.1 MB 长按或扫码关注我的公众号一起加油、一起学习进步
