Count Triplets in Array

mediumSave

ArraySortingTwo Pointers

Given an array of integers, your task is to count the number of triplets (triplets mean a group of three different indices) such that the sum of two numbers equals the third number. Specifically, you need to find triplets (i, j, k) where i < j < k and arr[i] + arr[j] == arr[k].

Example 1

Input

[
  1,
  1,
  2,
  2,
  3
]

Output

Explanation. The triples (0, 1, 2) and (1, 3, 4) satisfy the condition because 1+1=2 and 2+1=3.

Example 2

Input

[
  1,
  5,
  3,
  2,
  5
]

Output

Explanation. The triple (2, 3, 1) satisfies the condition because 3+2=5.

Example 3

Input

[
  3,
  3,
  3
]

Output

Explanation. No such indices (i, j, k) exist in this array where i < j < k and the sum of elements at indices i and j equals the element at index k.

Follow-up: Can you optimize your solution to achieve better than O(n^3) time complexity?

Constraints:

1. The length of the array will be at least 3 and no more than 1000.\n2. All the elements in the array are non-negative integers not exceeding 10,000.

Views: 2