⚡Flashcard Drill➔
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

  1. Sort the array. Fix the smallest index i, then use two pointers on the remaining suffix.
  2. If nums[i] + nums[l] + nums[r] < target, then every pair (l, l+1), ..., (l, r) also works, contributing r - l triplets at once.
  3. That counting shortcut is what turns the O(n^3) brute force into O(n^2).
  4. If the sum is too large, decrement r; otherwise increment l.

💻 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 - l counts them in bulk.
  • Using <= for the comparison: the sum must be strictly less than target.
  • Forgetting the sort: the bulk counting relies on the sorted order making all pairs with a given l valid.
  • Advancing r on a valid sum: the correct move is l += 1, since a larger l may 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.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems