Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/1099.html
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
Algorithm
(brute force) O(n^2)
Enumerate i and j, and then find the maximum value less than K.
time complexity
- Two-level loop traversal, so the time complexity is O(n^2)).
Space complexity
- Only a constant number of traversals are needed, so the space complexity is O(1).
Code
-
import java.util.Arrays; public class Two_Sum_Less_Than_K { class Solution { public int twoSumLessThanK(int[] A, int K) { int res = -1; if(A == null || A.length == 0){ return res; } Arrays.sort(A); int l = 0; int r = A.length-1; while(l<r){ int sum = A[l] + A[r]; if(sum < K){ res = Math.max(res, sum); l++; }else{ r--; } } return res; } } } ############ class Solution { public int twoSumLessThanK(int[] nums, int k) { Arrays.sort(nums); int ans = -1; int i = 0, j = nums.length - 1; while (i < j) { int t = nums[i] + nums[j]; if (t < k) { ans = Math.max(ans, t); ++i; } else { --j; } } return ans; } }
-
// OJ: https://leetcode.com/problems/two-sum-less-than-k/ // Time: O(N) // Space: O(1) class Solution { public: int twoSumLessThanK(vector<int>& A, int k) { sort(begin(A), end(A)); int i = 0, j = A.size() - 1, ans = INT_MIN; while (i < j) { int sum = A[i] + A[j]; if (sum < k) { ans = max(ans, sum); ++i; } else --j; } return ans == INT_MIN ? -1 : ans; } };
-
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
-
func twoSumLessThanK(nums []int, k int) int { sort.Ints(nums) ans := -1 i, j := 0, len(nums)-1 for i < j { if t := nums[i] + nums[j]; t < k { ans = max(ans, t) i++ } else { j-- } } return ans } func max(a, b int) int { if a > b { return a } return b }
-
function twoSumLessThanK(nums: number[], k: number): number { nums.sort((a, b) => a - b); let ans = -1; for (let i = 0, j = nums.length - 1; i < j; ) { const s = nums[i] + nums[j]; if (s < k) { ans = Math.max(ans, s); ++i; } else { --j; } } return ans; }