Accepted and Simple Java O(n^2) solution with detailed explanation

• We sort the array first. Then, for each element, we use the two pointer approach to find the number of triplets that meet the requirements.

Let me illustrate how the two pointer technique works with an example:

``````target = 2

i  lo    hi
[-2, 0, 1, 3]
``````

We use a for loop (index i) to iterate through each element of the array. For each i, we create two pointers, lo and hi, where lo is initialized as the next element of i, and hi is initialized at the end of the array. If we know that nums[i] + nums[lo] + nums[hi] < target, then we know that since the array is sorted, we can replace hi with any element from lo+1 to nums.length-1, and the requirements will still be met. Just like in the example above, we know that since -2 + 0 + 3 < 2, we can replace hi (3) with 1, and it would still work. Therefore, we can just add hi - lo to the triplet count.

``````public class Solution {
public int threeSumSmaller(int[] nums, int target) {
int result = 0;
Arrays.sort(nums);
for(int i = 0; i <= nums.length-3; i++) {
int lo = i+1;
int hi = nums.length-1;
while(lo < hi) {
if(nums[i] + nums[lo] + nums[hi] < target) {
result += hi - lo;
lo++;
} else {
hi--;
}
}
}
return result;
}
}``````

Thankyou

• great explanation! thanks for taking your time.

• really elegant solution, endorse you!

• Explanations are amazing! Good work keep it up

• I'm really fond of your explanation! Great job!

• Thanks for the explanation man!!! ðŸ˜˜ðŸ˜˜

• If we know that nums[i] + nums[lo] + nums[hi] < target, then we know that since the array is sorted, we can replace hi with any element from lo+1 to nums.length-1, and the requirements will still be met.

One thing I don't quite understand is that
why
replacing hi with any element from lo+1 to nums.length-1 can still meet the requirement
but not
replacing hi with any element from lo+1 to hi-1 ?

since numbers between hi+1 to nums.length-1 is greater than hi, replacing hi with these numbers would not be smaller than target.

Thanks!

• I understood adding high-low to result but in that case why still increment low++ ? cant we move to next i

• Great solution with nice explanation

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.