💬 Discord
Sign In
NeetCode #194LC-1099EasyTwo Pointers
← Back to All Problems

#194 · #1099 · Two Sum Less Than K(小于 K 的两数之和)

📌 Problem Statement & Constraints

Given an array nums and an integer k, return the maximum nums[i] + nums[j] where i < j and the sum is less than k. If no such pair exists, return -1. Constraints: 1 <= nums.length <= 100, 1 <= nums[i] <= 1000, 0 <= k <= 2000.

💡 Core Algorithmic Approaches

  1. Sort the array and use two pointers at the ends.
  2. If the sum is less than k, record it as a candidate and move the left pointer right to try for a larger sum.
  3. If the sum is at least k, move the right pointer left to reduce it.
  4. Because we want the largest sum strictly below k, sorting is essential -- an unsorted two-pointer scan has no such monotone structure.

💻 Benchmark Python3 Implementation

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        i, j = 0, len(nums) - 1
        best = -1
        while i < j:
            s = nums[i] + nums[j]
            if s < k:
                best = max(best, s)    # valid candidate
                i += 1                 # try to get closer to k
            else:
                j -= 1                 # too large
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates; the scan is O(n).
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Using <= k: the sum must be strictly less than k.
  • Returning 0 when no pair exists: the answer must be -1, and 0 is not achievable given nums[i] >= 1.
  • Skipping the sort: without sortedness, moving a pointer has no predictable effect on the sum.
  • Sorting and then returning the pair's indices: this variant returns the sum, not indices.