Solution

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

The brute force approach is to find every possible triplets $$(i, j, k)$$ subjected to $$i < j < k$$ and test for the condition.

Complexity analysis

\n
• \n

  Time complexity : $$O(n^3)$$ .\nThe total number of such triplets is $$\\binom{n}{3}$$ , which is $$\\frac{n!}{(n - 3)! \\times 3!} = \\frac{n \\times (n - 1) \\times (n - 2)}{6}$$ . Therefore, the time complexity of the brute force approach is $$O(n^3)$$ .

  \n
\n
• \n

  Space complexity : $$O(1)$$ .

  \n
\n

Approach #2 (Binary Search) [Accepted]

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

\n

Given a $$nums$$ array, find the number of index pairs $$i$$ , $$j$$ with $$0 \\leq i < j < n$$ that satisfy the condition $$nums[i] + nums[j] < target$$ \n

\n

If we sort the array first, then we could apply binary search to find the largest index $$j$$ such that $$nums[i] + nums[j] < target$$ for each $$i$$ . Once we found that largest index $$j$$ , we know there must be $$j-i$$ pairs that satisfy the above condition with $$i$$ \'s value fixed.

Finally, 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 $$(\\frac{left+right+1}{2})$$ instead of the lower middle element $$(\\frac{left+right}{2})$$ . The reason is due to the terminating condition when there are two elements left. If we chose the lower middle element and the condition $$nums[mid] < target$$ evaluates to true, then the loop will never terminate. Choosing the upper middle element will guarantee termination.

Complexity analysis

\n
• \n

  Time complexity : $$O(n^2 \\log n)$$ .\nThe binarySearch function takes $$O(\\log n)$$ time, therefore the twoSumSmaller takes $$O(n \\log n)$$ time. The threeSumSmaller wraps with another for-loop, and therefore is $$O(n^2 \\log n)$$ time.

  \n
\n
• \n

  Space complexity : $$O(1)$$ .

  \n
\n

Approach #3 (Two Pointers) [Accepted]

Let us try sorting the array first. For example, $$nums = [3,5,2,8,1]$$ becomes $$[1,2,3,5,8]$$ .

Let us look at an example $$nums = [1,2,3,5,8]$$ , and $$target = 7$$ .

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

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

When we look at the sum of first and last element, it is $$1 + 8 = 9$$ , which is $$\\geq target$$ . That tells us no index pair will ever contain the index $$right$$ . So the next logical step is to move the right pointer one step to its left.

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

Now the pair sum is $$1 + 5 = 6$$ , which is $$< target$$ . How many pairs with one of the $$index = left$$ that satisfy the condition? You can tell by the difference between $$right$$ and $$left$$ which is $$3$$ , namely $$(1,2), (1,3),$$ and $$(1,5)$$ . Therefore, we move $$left$$ one step to its right.

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    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 : $$O(n^2)$$ .\nThe twoSumSmaller function takes $$O(n)$$ time because both left and right traverse at most n steps. Therefore, the overall time complexity is $$O(n^2)$$ .

  \n
\n
• \n

  Space complexity : $$O(1)$$ .

  \n
\n