This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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`

.

For example, given *nums* = `[-2, 0, 1, 3]`

, and *target* = 2.

Return 2. 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*(*n*^{2}) runtime?

b'

\n## Solution

\n

\n#### Approach #1 (Brute Force) [Time Limit Exceeded]

\n

\n#### Approach #2 (Binary Search) [Accepted]

\n\n

\n#### Approach #3 (Two Pointers) [Accepted]

\n\n\n\n

'
\n\n

\n\n

The brute force approach is to find every possible triplets subjected to and test for the condition.

\n**Complexity analysis**

- \n
- \n
Time complexity : .\nThe total number of such triplets is , which is . Therefore, the time complexity of the brute force approach is .

\n \n - \n
Space complexity : .

\n \n

\n

Before we solve this problem, it is helpful to first solve this simpler *twoSum* version.

\n\nGiven a array, find the number of index pairs , with that satisfy the condition \n

\n

If we sort the array first, then we could apply binary search to find the largest index such that for each . Once we found that largest index , we know there must be pairs that satisfy the above condition with \'s value fixed.

\nFinally, we can now apply the *twoSum* solution to *threeSum* directly by wrapping an outer for-loop around it.

public int threeSumSmaller(int[] nums, int target) {\n Arrays.sort(nums);\n int sum = 0;\n for (int i = 0; i < nums.length - 2; i++) {\n sum += twoSumSmaller(nums, i + 1, target - nums[i]);\n }\n return sum;\n}\n\nprivate int twoSumSmaller(int[] nums, int startIndex, int target) {\n int sum = 0;\n for (int i = startIndex; i < nums.length - 1; i++) {\n int j = binarySearch(nums, i, target - nums[i]);\n sum += j - i;\n }\n return sum;\n}\n\nprivate int binarySearch(int[] nums, int startIndex, int target) {\n int left = startIndex;\n int right = nums.length - 1;\n while (left < right) {\n int mid = (left + right + 1) / 2;\n if (nums[mid] < target) {\n left = mid;\n } else {\n right = mid - 1;\n }\n }\n return left;\n}\n

Note that in the above binary search we choose the upper middle element instead of the lower middle element . The reason is due to the terminating condition when there are two elements left. If we chose the lower middle element and the condition evaluates to true, then the loop will never terminate. Choosing the upper middle element will guarantee termination.

\n**Complexity analysis**

- \n
- \n
Time complexity : .\nThe

\n*binarySearch*function takes time, therefore the*twoSumSmaller*takes time. The*threeSumSmaller*wraps with another for-loop, and therefore is time. \n - \n
Space complexity : .

\n \n

\n

Let us try sorting the array first. For example, becomes .

\nLet us look at an example , and .

\n[1, 2, 3, 5, 8]\n \xe2\x86\x91 \xe2\x86\x91\nleft right\n

Let us initialize two indices, and pointing to the first and last element respectively.

\nWhen we look at the sum of first and last element, it is , which is . That tells us no index pair will ever contain the index . So the next logical step is to move the right pointer one step to its left.

\n[1, 2, 3, 5, 8]\n \xe2\x86\x91 \xe2\x86\x91\nleft right\n

Now the pair sum is , which is . How many pairs with one of the that satisfy the condition? You can tell by the difference between and which is , namely and . Therefore, we move one step to its right.

\npublic int threeSumSmaller(int[] nums, int target) {\n Arrays.sort(nums);\n int sum = 0;\n for (int i = 0; i < nums.length - 2; i++) {\n sum += twoSumSmaller(nums, i + 1, target - nums[i]);\n }\n return sum;\n}\n\nprivate int twoSumSmaller(int[] nums, int startIndex, int target) {\n int sum = 0;\n int left = startIndex;\n int right = nums.length - 1;\n while (left < right) {\n if (nums[left] + nums[right] < target) {\n sum += right - left;\n left++;\n } else {\n right--;\n }\n }\n return sum;\n}\n

**Complexity analysis**

- \n
- \n
Time complexity : .\nThe

\n*twoSumSmaller*function takes time because both*left*and*right*traverse at most*n*steps. Therefore, the overall time complexity is . \n - \n
Space complexity : .

\n \n