# Problem 259: 3Sum Smaller

> [https://leetcode.com/problems/3sum-smaller/#/description](https://leetcode.com/problems/3sum-smaller/#/description)

![](https://1241747088-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lpv9LvBSlFaukf_ALqh%2F-Lpv9NPw3Ji1X5Vk8CES%2F-Lpv9yN2GNzrnAlDXui0%2F259.png?generation=1569729545457791\&alt=media)

## 思路

* 双指针法：遍历 i 的时候， 用 left 和 right 从两边向中间逼近
* 注意：一定要 sort 原来的 Array

```java
public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;
        int count = 0, len = nums.length;

        Arrays.sort(nums);
        for (int i = 0; i < len - 2; i++) {
            int left = i + 1, right = len - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < target) {
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }

        return count;
    }
}
```
