图解「小于 K 的两数之和 」

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

图解「小于 K 的两数之和 」

作者 | P.yh

来源 | 五分钟学算法

题目描述

题目来源于 LeetCode 上第 1099 号问题:小于 K 的两数之和。

给你一个整数数组 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. 1 <= A.length <= 100

  2. 1 <= A[i] <= 1000

  3. 1 <= K <= 2000

题目解析

传统的 TwoSum 都是要你找到等于 target 的配对,那么如果说要找到 大于/小于 target 的配对呢?

这个时候 Hash 表的方法就很难 work 了,因为 Hash 表比较适合处理 等于 的情况 !

那么就需要考虑如何使用排序加双指针的方法来解决这个问题,这里,题目是要求小于 target 的数量,我们还是按照之前的分析思路来分析。

如果说当前左右指针指向的元素的和大于或者等于 target,那么势必我们需要向左移动右指针,让两个元素的和尽可能地小。

当前头尾指针指向的元素和小于 target 的时候,这时我们需要记录答案,虽然这道题目里面没提,如果说要记录配对数量的话,这时并不是记录一个答案,如果说当前左指针固定,除了当前的右指针指向的元素,在左指针和右指针之间的数都是满足要求的,我们只需要加上这个区间的数量即可。

当然如果数组中存在重复元素,那么我们就需要按照之前的套路遍历去重了,当然对于这道题来说,我们选择满足条件的最大值即可。

动画描述

代码实现

public int twoSumLessThanK(int[] A, int K) {
    if (A == null || A.length == 0) {
        return -1;
    }

    Arrays.sort(A);

    int l = 0, r = A.length - 1;
    int result = Integer.MIN_VALUE;

    while (l < r) {
        if (A[l] + A[r] >= K) {
            r--;
        } else {
            result = Math.max(result, A[l] + A[r]);
            l++;
        }
    }

    return result == Integer.MIN_VALUE ? -1 : result;
}


图解「小于 K 的两数之和 」

有热门推荐👇


1.程序员全球最厉害的 14 位程序员

2.【GitHub我在 GitHub 上看到了一个丧心病狂的开源项目!

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!


图解「小于 K 的两数之和 」

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 图解「小于 K 的两数之和 」

我还会在以下平台发布内容

GitHub 哔哩哔哩