1099 Two Sum Less Than K

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

这题一开始没认真审题，以为是L609 Two Sum V认真看了才发现，原来找的是closet，所以去看了16 3 Sum Closest。但其实更像L553 Two Sum Closest这里自己维护了一个diff，看了答案，其实可以直接用一个max来track。这个max只能在less than的时候才ok。L553那里可能是above的。T:O(nlogn), S:O(1)

// my 解法
public int twoSumLessThanK(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return -1;
    }

    int left = 0;
    int right = nums.length - 1;
    Arrays.sort(nums);
    int ans = -1;
    int minDiff = Integer.MAX_VALUE;
    while (left < right) {
        int sum = nums[left] + nums[right];
        int diff = Math.abs(k - sum);
        if (sum < k) {
            if (diff < minDiff) {
                minDiff = diff;
                ans = sum;
            }
            left++;
        } else if (sum >= k) {
            right--;
        }
    }

    return ans;
}

// leetcode 答案
public int twoSumLessThanK(int[] nums, int k) {
    Arrays.sort(nums);
    int answer = -1;
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum < k) {
            answer = Math.max(answer, sum);
            left++;
        } else {
            right--;
        }
    }
    return answer;
}