• Time:O(n^2)
• Space:O(1)

## C++

``````class Solution {
public:
int threeSumSmaller(vector<int>& nums, int target) {
if (nums.size() < 3)
return 0;

int ans = 0;

sort(begin(nums), end(nums));

for (int i = 0; i + 2 < nums.size(); ++i) {
int l = i + 1;
int r = nums.size() - 1;
while (l < r)
if (nums[i] + nums[l] + nums[r] < target) {
// (nums[i], nums[l], nums[r])
// (nums[i], nums[l], nums[r - 1])
// ...,
// (nums[i], nums[l], nums[l + 1])
ans += r - l;
++l;
} else {
--r;
}
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums.length < 3)
return 0;

int ans = 0;

Arrays.sort(nums);

for (int i = 0; i + 2 < nums.length; ++i) {
int l = i + 1;
int r = nums.length - 1;
while (l < r)
if (nums[i] + nums[l] + nums[r] < target) {
// (nums[i], nums[l], nums[r])
// (nums[i], nums[l], nums[r - 1])
// ...,
// (nums[i], nums[l], nums[l + 1])
ans += r - l;
++l;
} else {
--r;
}
}

return ans;
}
}
``````

## Python

``````class Solution:
def threeSumSmaller(self, nums: List[int], target: int) -> int:
if len(nums) < 3:
return 0

ans = 0

nums.sort()

for i in range(len(nums) - 2):
l = i + 1
r = len(nums) - 1
while l < r:
if nums[i] + nums[l] + nums[r] < target:
# (nums[i], nums[l], nums[r])
# (nums[i], nums[l], nums[r - 1])
# ...,
# (nums[i], nums[l], nums[l + 1])
ans += r - l
l += 1
else:
r -= 1

return ans
``````