首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 1099. 小于 K 的两数之和(二分查找)

LeetCode 1099. 小于 K 的两数之和(二分查找)

作者头像
Michael阿明
发布2020-07-13 16:11:42
7780
发布2020-07-13 16:11:42
举报

1. 题目

给你一个整数数组 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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/two-sum-less-than-k 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

2.1 暴力

class Solution {
public:
    int twoSumLessThanK(vector<int>& 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 mindiff==INT_MAX ? -1 : sum;
    }
};

4 ms 9.2 MB

2.2 二分查找

  • 排序
  • 固定一个数,二分查找另一个数
class Solution {
public:
    int twoSumLessThanK(vector<int>& 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(mid==A.size()-1 || A[mid+1] >= t)
    				{	//找到了 
    					if(mid != i && K-A[mid]-A[i] < mindiff)
    					{	//不是同一个数,且更接近
    						mindiff = K-A[mid]-A[i];
    						sum = A[mid]+A[i];
    					}
    					break;
    				}
    				else
    					l = mid+1;
    			}
    		}
    	}
    	return mindiff==INT_MAX ? -1 : sum;
    }
};

4 ms 9.1 MB

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-07-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
    • 2.1 暴力
      • 2.2 二分查找
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档