Given an array nums
of integers and integer k
, return the maximum sum
such that there exists i < j
with nums[i] + nums[j] = sum
and sum < k
. If no i
, j
exist satisfying this equation, return -1
.
Example 1:
Input: nums = [34,23,1,24,75,33,54,8], k = 60 Output: 58 Explanation: We can use 34 and 24 to sum 58 which is less than 60.
Example 2:
Input: nums = [10,20,30], k = 15 Output: -1 Explanation: In this case it is not possible to get a pair sum less that 15.
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 1000
1 <= k <= 2000
小于 K 的两数之和。
给定一个数组 A,再给定一个数 k,要求找出 A 中的两个数,使得它们的和小于 k,返回这样的和里最大的那个和。
————————————————
版权声明:本文为CSDN博主「记录算法题解」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_46105170/article/details/105592564
题目不难,但是因为是带锁的题,所以记录一下。
时间O(nlogn)
空间O(1)
Java实现
1 class Solution { 2 public int twoSumLessThanK(int[] nums, int k) { 3 Arrays.sort(nums); 4 int left = 0; 5 int right = nums.length - 1; 6 int res = -1; 7 while (left < right) { 8 int sum = nums[left] + nums[right]; 9 if (sum < k) { 10 res = Math.max(res, sum); 11 left++; 12 } else { 13 right--; 14 } 15 } 16 return res; 17 } 18 }
原文地址:http://www.cnblogs.com/cnoodle/p/16906129.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性