Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 259 with 14 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 259 # by problem number
lcpy gen -s three_sum_smaller # by problem name
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.
Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]
Input: nums = [], target = 0
Output: 0
Input: nums = [0], target = 0
Output: 0
n == nums.length0 <= n <= 3500-100 <= nums[i] <= 100-100 <= target <= 10010^9.class Solution:
# Time: O(n^2)
# Space: O(1) excluding sort
def three_sum_smaller(self, nums: list[int], target: int) -> int:
nums = sorted(nums)
count = 0
n = len(nums)
for i in range(n - 2):
j, k = i + 1, n - 1
while j < k:
if nums[i] + nums[j] + nums[k] < target:
count += k - j
j += 1
else:
k -= 1
return count
| Time | Space |
|---|---|
| O(n^2) | O(1) excluding sort |