3Sum Smaller
Find Index Triplets
Given an array of n integers nums and an integer 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 1:
Input: nums = [-2, 0, 1, 3], target = 2
Output: 2
Explanation: There are two triplets which sums are less than 2: [-2, 0, 1] and [-2, 0, 3].
Example 2:
Input: nums = [], target = 0
Output: 0
Example 3:
Input: nums = [0], target = 0
Output: 0
Constraints:
n == nums.length
0 ≤ n ≤ 3500
-100 ≤ nums[i] ≤ 100
-100 ≤ target ≤ 100
Approach: Binary Search
Before we solve the threeSum problem, solve this simpler twoSum version:
Given a nums array, find the number of index pairs i, j with 0 ≤ i < j < n that satisfy the condition nums[i] + nums[j] < target.
If we sort the array first, we can apply binary search to find the largest index j such that nums[i] + nums[j] < target for each i. Once we find the largest index j, we know there must be j - i pairs that satisfy the condition with i's value fixed. Finally, we can apply the twoSum solution to threeSum directly by wrapping an outer for-loop around it.
class Solution {
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length - 2; i++) {
sum += twoSumSmaller(nums, i + 1, target - nums[i]);
}
return sum;
}
private int twoSumSmaller(int[] nums, int startIndex, int target) {
int sum = 0;
for (int i = startIndex; i < nums.length - 1; i++) {
int j = binarySearch(nums, i, target - nums[i]);
sum += j - i;
}
return sum;
}
private int binarySearch(int[] nums, int startIndex, int target) {
int left = startIndex;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right + 1) / 2;
if (nums[mid] < target) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}
Complexity Analysis
Time Complexity: O(n2 log n). The binarySearch function takes O(log n) time, so the twoSumSmaller function takes O(n log n) time. The threeSumSmaller function wraps with another for-loop, resulting in O(n2 log n) time complexity.
Space Complexity: O(1). No additional data structures are used.
