题目描述

给定一个整数数组 A 和整数 K，返回最大的 S 使得存在 i < j， A[i] + A[j] = S 且 S < K。如果不存在满足等式的 i 和 j，返回 -1。

样例

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

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

提示

1. 1 <= A.length <= 100
2. 1 <= A[i] <= 1000
3. 1 <= K <= 2000

算法

(暴力枚举) $O(n^2)$

1. 暴力枚举 i 和 j，然后找到小于 K 的情况下的最大值。

时间复杂度

• 两层循环遍历，故时间复杂度为 $O(n^2)$。

空间复杂度

• 仅需要常数个遍历，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        int n = A.size();
        int ans = -1;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (A[i] + A[j] < K)
                    ans = max(ans, A[i] + A[j]);

        return ans;
    }
};