Two Pointer Algorithm to Find Maximum Two Sum Less Than K

  • 时间:2020-09-24 11:54:15
  • 分类:网络文摘
  • 阅读:93 次

Given an array A of integers and integer K, return the maximum S such that there exists i < j with A[i] + A[j] = S and S < K. If no i, j exist satisfying this equation, return -1.

Example 1:
Input: A = [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: A = [10,20,30], K = 15
Output: -1
Explanation:
In this case it’s not possible to get a pair sum less that 15.

Note:

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

Intutive Bruteforce Algorithm to Find Maximum Tow Sum Pair Less than K

The bruteforce is the most intutive algorithm that we can use. We can bruteforce the two-pair in O(N^2) time complexity. Then, if the sum is less than K, we record the maxium.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        int r = -1;
        for (int i = 0; i < A.size(); ++ i) {
            for (int j = i + 1; j < A.size(); ++ j) {
                if (A[i] + A[j] < K) {
                    r = max(r, A[i] + A[j]);
                }
            }
        }
        return r;
    }
};
class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        int r = -1;
        for (int i = 0; i < A.size(); ++ i) {
            for (int j = i + 1; j < A.size(); ++ j) {
                if (A[i] + A[j] < K) {
                    r = max(r, A[i] + A[j]);
                }
            }
        }
        return r;
    }
};

The above C++ bruteforce two-pair algorithm takes O(1) constant space.

Sort and Two Pointer Algorithm to Find Maximum Tow Sum Pair Less than K

If we sort the array which takes O(nlogN) time, we can apply the two-pointer algorithm by initialising the two points at two ends. If the current sum is less than K, we record and update the maximum. At each iteration, depending on the comparison between K and the current sum, we move the corresponding pointer.

The two pointer algorithm takes O(N), and overall the complexity is O(nlogN).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        sort(begin(A), end(A));
        int i = 0;
        int j = A.size() - 1;
        int ans = -1;
        while (i < j) {
            if (A[i] + A[j] >= K) {
                j --;
            } else {
                ans = max(ans, A[i] + A[j]);
                i ++;
            }
        }
        return ans;
    }
};
class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        sort(begin(A), end(A));
        int i = 0;
        int j = A.size() - 1;
        int ans = -1;
        while (i < j) {
            if (A[i] + A[j] >= K) {
                j --;
            } else {
                ans = max(ans, A[i] + A[j]);
                i ++;
            }
        }
        return ans;
    }
};

Same algorithm but implemented in Python3 is given as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def twoSumLessThanK(self, A: List[int], K: int) -> int:
        A = sorted(A)
        ans = -1
        j = 0
        k = len(A) - 1
        while j < k:
            if A[j] + A[k] < K:
                ans = max(ans, A[j] + A[k])
                j += 1
            else:
                k -= 1
        return ans
class Solution:
    def twoSumLessThanK(self, A: List[int], K: int) -> int:
        A = sorted(A)
        ans = -1
        j = 0
        k = len(A) - 1
        while j < k:
            if A[j] + A[k] < K:
                ans = max(ans, A[j] + A[k])
                j += 1
            else:
                k -= 1
        return ans

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
读《圆明园的毁灭》有感550字  打赌作文700字  支教组老师心得  以“软”实力讲“硬”道理–国展书家李冰侧记  子产论尹何为邑原文及翻译  子产坏晋馆垣原文及翻译  季札观周乐/季札观乐原文及翻译  百家讲坛系列节目《汉代风云人物》MP3蓝奏云下载  晏子不死君难原文及翻译  子产告范宣子轻币原文及翻译 
评论列表
添加评论