title: Java - find all combinations of three numbers in sorted array that have a sum smaller than a number
body: <p>The title is a mouthful so I will explain further. This is a question out of a practice test for my introduction to computer science course. Most of the questions I was able to solve by myself or find a solution online, but not for this one.</p>
  <p>You are given a sorted array (<code>int[] arr</code>) of unique integers (positive and negative). You must find how many triplets (combinations of three numbers in the array) have a sum that is less than a given number (<code>int num</code>).</p>
  <p>The method signature is:
  <code>public static int countTriplets (int [] arr, int num)</code></p>
  <p>The catch is that it must be done with the lowest possible time complexity. If I understand correctly, iterating over all the possible combinations with nested for loops would give me a time complexity of O(n^3). However, I can't think of any other solution.</p>
  <p>I should also mention that the array should be used as an array, without using other Java classes like ArrayList.</p>
  <p>Any help is appreciated. It doesn't have to be a complete solution in code, even just a general idea of how to solve this.</p>