NeetCode #217LC-259MediumTwo Pointers
← Back to All Problems#217 · #259 · 3Sum Smaller(较小的三数之和)
📌 Problem Statement & Constraints
Given an array of integers
nums and an integer target, return the number of index triplets i < j < k such that nums[i] + nums[j] + nums[k] < target. Constraints: 0 <= nums.length <= 3500, -100 <= nums[i] <= 100, -100 <= target <= 100.💡 Core Algorithmic Approaches
- Sort the array. Fix the smallest index
i, then use two pointers on the remaining suffix. - If
nums[i] + nums[l] + nums[r] < target, then every pair(l, l+1), ..., (l, r)also works, contributingr - ltriplets at once. - That counting shortcut is what turns the O(n^3) brute force into O(n^2).
- If the sum is too large, decrement
r; otherwise incrementl.
💻 Benchmark Python3 Implementation
class Solution:
def threeSumSmaller(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
res = 0
for i in range(n - 2):
l, r = i + 1, n - 1
while l < r:
if nums[i] + nums[l] + nums[r] < target:
res += r - l # all pairs with this l work
l += 1
else:
r -= 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the sort plus a two-pointer scan for each fixed index.
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Counting one triplet at a time: O(n^3) and unnecessary;
r - lcounts them in bulk. - Using
<=for the comparison: the sum must be strictly less thantarget. - Forgetting the sort: the bulk counting relies on the sorted order making all pairs with a given
lvalid. - Advancing
ron a valid sum: the correct move isl += 1, since a largerlmay still admit valid pairs.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.