---
description: https://leetcode.com/problems/3sum-smaller/
---

# 259. 3Sum Smaller

Given an array of n integers nums and a 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`.

**Example:**

```
Input: nums = [-2,0,1,3], and target = 2
Output: 2 
Explanation: Because there are two triplets which sums are less than 2:
             [-2,0,1]
             [-2,0,3]
```

**Follow up:** Could you solve it in O(n2) runtime?

## Thoughts

对给定数组统计满足和小于target的三元组个数。2 Sum。排序并遍历i，在\[0, i - 1]范围内维持首尾双指针l和r，\[l, r]看作当前问题范围，当它俩加起来< target - nums\[i]时说明\[l+1, r]所有数都能和nums\[l]拼成合法对，res += r - l，跳过l；否则说明\[l, r - 1]中任何数都不能和nums\[r]组成合法对，r--。&#x20;

## Code

```python
class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        for i, num in enumerate(nums):
            j, k = 0, i - 1
            while j < k:
                if nums[j] + nums[k] < target - num:
                    res += k - j
                    j += 1
                else:
                    k -= 1
        return res
```

```java
class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        int res = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int t = target - nums[i];
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                if (nums[l] + nums[r] < t) {
                    res += r - l;
                    l++;
                } else {
                    r--;
                }
            }
        }

        return res;
    }
}
```

## Analysis

时间复杂度O(N^2).
