Skip to content

Latest commit

 

History

History
122 lines (93 loc) · 2.82 KB

File metadata and controls

122 lines (93 loc) · 2.82 KB

English Version

题目描述

给你一个整数数组 nums 和整数 k ,返回最大和 sum ,满足存在 i < j 使得 nums[i] + nums[j] = sumsum < k 。如果没有满足此等式的 i,j 存在,则返回 -1

 

示例 1:

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

示例 2:

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

 

提示:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 1000
  • 1 <= k <= 2000

解法

先进行排序,再用双指针 lowhigh 分别指向排序数组的首尾,遍历获取满足条件的和 nums[low] + nums[high] 并求最大和。

Python3

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        low, high = 0, len(nums) - 1
        res = -1
        while low < high:
            val = nums[low] + nums[high]
            if val < k:
                res = max(res, val)
                low += 1
            else:
                high -= 1
        return res

Java

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);
        int low = 0, high = nums.length - 1;
        int res = -1;
        while (low < high) {
            int val = nums[low] + nums[high];
            if (val < k) {
                res = Math.max(res, val);
                ++low;
            } else {
                --high;
            }
        }
        return res;
    }
}

C++

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int low = 0, high = nums.size() - 1;
        int res = -1;
        while (low < high) {
            int val = nums[low] + nums[high];
            if (val < k) {
                res = max(res, val);
                ++low;
            } else {
                --high;
            }
        }
        return res;
    }
};

...