3sum smaller

Array Two Pointers Binary Search Sorting

51.3% acceptance

Mar 31, 2026

1630

169

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn three_sum_smaller(mut nums: Vec<i32>, target: i32) -> i32 {
    if nums.len() < 3 { return 0; }
    nums.sort_unstable();
    let mut count = 0;
    let n = nums.len();
    for i in 0..n - 2 {
      let mut lo = i + 1;
      let mut hi = n - 1;
      while lo < hi {
        if nums[i] + nums[lo] + nums[hi] < target {
          count += (hi - lo) as i32;
          lo += 1;
        } else {
          hi -= 1;
        }
      }
    }
    count
  }
}