title: Find the total number of triplets when summed are less than a given threshold
body: <p>So I'm working on some practice problems and having trouble reducing the complexity. I am given an array of distinct integers a[] and a threshold value T. I need to find the number of triplets <code>i</code>,<code>j</code>,<code>k</code> such that <code>a[i] &lt; a[j] &lt; a[k]</code> and <code>a[i] + a[j] + a[k] &lt;= T</code>. I've gotten this down from <code>O(n^3)</code> to <code>O(n^2 log n)</code> with the following python script. I'm wondering if I can optimize this any further.</p>
  
  <pre><code>import sys
  import bisect
  
  first_line = sys.stdin.readline().strip().split(' ')
  num_numbers = int(first_line[0])
  threshold = int(first_line[1])
  count = 0
  
  if num_numbers &lt; 3:
      print count
  else:
      numbers = sys.stdin.readline().strip().split(' ')
      numbers = map(int, numbers)
      numbers.sort()
  
      for i in xrange(num_numbers - 2):
          for j in xrange(i+1, num_numbers - 1):
              k_1 = threshold - (numbers[i] + numbers[j])
              if k_1 &lt; numbers[j]:
                  break
              else:
                  cross_thresh = bisect.bisect(numbers,k_1) - (j+1)
                  if cross_thresh &gt; 0:
                      count += cross_thresh
  
      print count
  </code></pre>
  
  <p>In the above example, the first input line simply provides the number of numbers and the threshold. The next line is the full list. If the list is less than 3, there is no triplets that can exist, so we return 0. If not, we read in the full list of integers, sort them, and then process them as follows: we iterate over every element of <code>i</code> and <code>j</code> (such that i &lt; j) and we compute the highest value of k that would not break <code>i + j + k &lt;= T</code>. We then find the index (<code>s</code>) of the first element in the list that violates this condition and take all the elements between j and s and add them to the count. For 30,000 elements in a list, this takes about 7 minutes to run. Is there any way to make it faster?</p>