Algorithm-LeetCode/Solutions/1099.Two_Sum_Less_Than_K.py at main · ling67/Algorithm-LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""
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

"""

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        min_dis = float('inf')
        i, j = 0, len(nums) - 1
        while i < j:
            two_sum = nums[i] + nums[j]
            if two_sum == k:
                j -= 1
            elif two_sum < k:
                min_dis = min(min_dis, k - two_sum)
                i += 1
            else:
                j -= 1

        return -1 if min_dis == float('inf') else k - min_dis