Given an array of distinct integers. The task is to count all the triplets such that sum of two elements equals the third element.
 
Example 1: 
Input: 
N = 4 
arr[] = {1, 5, 3, 2}
Output: 2 
Explanation: There are 2 triplets:
 1 + 2 = 3 and 3 +2 = 5
Example 2: 
Input: 
N = 3
arr[] = {2, 3, 4}
Output: 0
Explanation: No such triplet exits
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countTriplet() which takes the array arr[] and N as inputs and returns the triplet count
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Amortized analysis

Starter code: #User function Template for python3

class Solution:

	def countTriplet(self, arr, n):

		# code here

Solutions:
class Solution:

	def countTriplet(self, array, n):
		array.sort()
		n = len(array)
		count = 0
		for i in range(n - 1, 1, -1):
			j = 0
			k = i - 1
			while j < k:
				if array[j] + array[k] == array[i]:
					count += 1
					j += 1
					k -= 1
				elif array[j] + array[k] < array[i]:
					j += 1
				else:
					k -= 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		count = 0
		s = set(arr)
		for i in range(n - 1):
			for j in range(i + 1, n):
				if arr[i] + arr[j] in s:
					count += 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		count = 0
		set1 = set(arr)
		z = {}
		for i in arr:
			z.setdefault(i, 0)
			z[i] += 1
		x = 0
		y = 0
		for i in range(n):
			for j in range(i + 1, n):
				x = 0
				y = 0
				if z[arr[i]] > 1:
					x = 1
				if z[arr[j]] > 1:
					y = 1
				if arr[i] + arr[j] in set1:
					count += z[arr[i] + arr[j]] - x - y
		return count


class Solution:

	def countTriplet(self, arr, n):
		l = []
		c = 0
		k = set(arr)
		for i in range(n - 1):
			for j in range(i + 1, n):
				if arr[i] + arr[j] in k:
					c += 1
		return c


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		count = 0
		for i in range(n):
			left = 0
			right = i - 1
			while left < right:
				if arr[i] == arr[left] + arr[right]:
					count += 1
					left += 1
				elif arr[i] < arr[left] + arr[right]:
					right -= 1
				else:
					left += 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		cnt = 0
		for i in range(0, n - 1):
			for j in range(i + 1, n):
				s = arr[i] + arr[j]
				if s in d:
					cnt += 1
		return cnt


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		count = 0
		if n <= 2:
			return count
		for i in range(n - 1, -1, -1):
			j = 0
			k = i - 1
			while k > j:
				if arr[j] + arr[k] == arr[i]:
					count += 1
					j += 1
					k -= 1
				elif arr[j] + arr[k] < arr[i]:
					j += 1
				else:
					k -= 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		count = 0
		index = 0
		for index in range(n):
			start = 0
			end = index - 1
			while start < end:
				sum = arr[start] + arr[end]
				if sum == arr[index]:
					count += 1
					start += 1
					end -= 1
				elif sum < arr[index]:
					start += 1
				else:
					end -= 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		map = {}
		currsum = 0
		triplets = 0
		for num in arr:
			map[num] = 0
		for i in range(n - 1):
			for j in range(i + 1, n):
				currsum = arr[i] + arr[j]
				if currsum in map:
					map[currsum] += 1
					triplets += 1
		return triplets


class Solution:

	def countTriplet(self, arr, n):
		h = set(arr)
		c = 0
		m = max(arr)
		arr.sort()
		for i in range(n - 1):
			for j in range(i + 1, n):
				if arr[i] + arr[j] in h:
					c += 1
				elif arr[i] + arr[j] > m:
					break
		return c


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		last = n - 1
		count = 0
		while last >= 0:
			j = last - 1
			dic = {}
			for i in range(j + 1):
				if arr[last] - arr[i] in dic:
					count += 1
				dic[arr[i]] = i
			last -= 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		count = 0
		d = {}
		for i in range(len(arr)):
			d[arr[i]] = i
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				temp = arr[i] + arr[j]
				if temp in d and d[temp] not in (i, j):
					count += 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		arr_set = set(arr)
		count = 0
		for i in range(0, n):
			x = arr[i]
			for j in range(i + 1, n):
				y = arr[j]
				if x + y in arr_set:
					count += 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		i = n - 1
		count = 0
		while i >= 0:
			j = 0
			k = i - 1
			while j < k:
				if arr[j] + arr[k] == arr[i]:
					count += 1
					j += 1
					k -= 1
				elif arr[j] + arr[k] < arr[i]:
					j += 1
				else:
					k -= 1
			i -= 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		h = set()
		for i in arr:
			h.add(i)
		count = 0
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				if arr[i] + arr[j] in h:
					count += 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		data = {}
		res = 0
		for each in arr:
			if each not in data:
				data[each] = 1
			else:
				data[each] += 1
		for i in range(n):
			for j in range(i + 1, n):
				req = arr[i] + arr[j]
				if arr[i] == 0 and arr[j] == 0 and (data[0] >= 3):
					res += 1
				elif arr[i] == 0 and data[arr[j]] > 1:
					res += 1
				elif arr[j] == 0 and data[arr[i]] > 1:
					res += 1
				elif req in data:
					res += 1
		return res


class Solution:

	def countTriplet(self, arr, n):
		ans = 0
		arr.sort()
		for i in range(n - 1, -1, -1):
			val = arr[i]
			top = i - 1
			bottom = 0
			while bottom < top:
				if arr[top] + arr[bottom] > val:
					top -= 1
				elif arr[top] + arr[bottom] < val:
					bottom += 1
				elif bottom != top:
					ans += 1
					top -= 1
		return ans


class Solution:

	def countTriplet(self, arr, n):
		d = {}
		counter = 0
		for el in range(len(arr)):
			d[arr[el]] = 1
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				if arr[i] + arr[j] in d:
					counter = counter + 1
		return counter


class Solution:

	def countTriplet(self, A, n):
		index = [0] * 1000000
		count = 0
		for i in range(n):
			index[A[i]] = 1
		for i in range(n - 1):
			for j in range(i + 1, n):
				if index[A[i] + A[j]] == 1:
					count += 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		count = 0
		for i in range(n - 1, -1, -1):
			l = 0
			r = i - 1
			while l < r:
				if arr[l] + arr[r] == arr[i]:
					count += 1
					l += 1
					r -= 1
				elif arr[l] + arr[r] > arr[i]:
					r -= 1
				else:
					l += 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		c = 0
		h = {}
		for i in arr:
			h[i] = 1
		for i in range(n):
			for j in range(i + 1, n):
				z = arr[i] + arr[j]
				if z in h.keys():
					c += 1
		return c


class Solution:

	def countTriplet(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		cnt = 0
		for i in range(n):
			d[arr[i]] -= 1
			for j in range(i + 1, n):
				d[arr[j]] -= 1
				summ = arr[i] + arr[j]
				if summ in d.keys() and d[summ] > 0:
					cnt += 1
				d[arr[j]] += 1
			d[arr[i]] += 1
		return cnt


class Solution:

	def countTriplet(self, a, n):
		c = 0
		a.sort()
		for i in range(n - 1, 2, -1):
			l = 0
			h = i - 1
			k = a[i]
			while l < h:
				if a[l] + a[h] == k:
					c += 1
					l += 1
					h -= 1
				elif a[l] + a[h] < k:
					l += 1
				else:
					h -= 1
		return c


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		count = 0
		i = n - 1
		while i >= 2:
			l = 0
			r = i - 1
			while l < r:
				if arr[l] + arr[r] == arr[i]:
					count += 1
					r -= 1
					l += 1
				elif arr[l] + arr[r] < arr[i]:
					l += 1
				else:
					r -= 1
			i -= 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		count = 0
		p = n - 1
		while p > 1:
			left = 0
			right = p - 1
			while left < right:
				if arr[left] + arr[right] == arr[p]:
					count += 1
					left += 1
				elif arr[left] + arr[right] < arr[p]:
					left += 1
				elif arr[left] + arr[right] > arr[p]:
					right -= 1
			p -= 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		c = 0
		dict = {}
		for i in arr:
			dict[i] = 0
		for i in range(n - 1):
			for j in range(i + 1, n):
				if arr[i] + arr[j] in dict:
					c += 1
		return c


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		count = 0
		i = n - 1
		while i > 1:
			target = arr[i]
			start = 0
			end = i - 1
			while start < end:
				if arr[start] + arr[end] == target:
					count += 1
					start += 1
					end -= 1
				elif arr[start] + arr[end] > target:
					end -= 1
				else:
					start += 1
			i -= 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		M = {}
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] + arr[j] in M:
					M[arr[i] + arr[j]] += 1
				else:
					M[arr[i] + arr[j]] = 1
		count = 0
		for i in range(n):
			if arr[i] in M and M[arr[i]] > 0:
				count += M[arr[i]]
				M[arr[i]] = 0
		return count


class Solution:

	def countTriplet(self, arr, n):
		ar = sorted(arr)
		i = n - 1
		cnt = 0
		while i >= 0:
			j = 0
			k = i - 1
			while j < k:
				if ar[j] + ar[k] == ar[i]:
					cnt += 1
				if ar[j] + ar[k] > ar[i]:
					k -= 1
				else:
					j += 1
			i -= 1
		return cnt


class Solution:

	def countTriplet(self, arr, n):
		map1 = {}
		for i in range(n):
			map1[arr[i]] = map1.get(arr[i], 0) + 1
		count = 0
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] + arr[j] in map1:
					count += 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		dct = {}
		for item in arr:
			dct[item] = dct.get(item, 0) + 1
		count = 0
		for i in range(n):
			for j in range(i + 1, n):
				a = arr[i] + arr[j]
				if a in dct:
					count += 1
		return count


class Solution:

	def twoSum(self, arr, target):
		hash_set = set()
		count = 0
		for num in arr:
			if num in hash_set:
				count += 1
			else:
				hash_set.add(target - num)
		return count

	def countTriplet(self, arr, n):
		result = 0
		for i in range(n):
			target = arr[i]
			newArray = arr[:i] + arr[i + 1:]
			result += self.twoSum(newArray, target)
		return result


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		count = 0
		for i in range(n):
			low = 0
			high = i - 1
			while low < high:
				if arr[low] + arr[high] == arr[i]:
					count += 1
					low += 1
					high -= 1
				elif arr[low] + arr[high] < arr[i]:
					low += 1
				elif arr[high] + arr[low] > arr[i]:
					high -= 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		ct = 0
		hmap = {}
		for i in arr:
			if i in hmap:
				hmap[i] += 1
			else:
				hmap[i] = 1
		for i in range(n):
			for j in range(i + 1, n):
				temp = arr[i] + arr[j]
				if temp in hmap:
					ct += 1
		return ct


class Solution:

	def countTriplet(self, arr, n):
		_d = {}
		_count = 0
		for i in arr:
			_d[i] = -1
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] + arr[j] in _d.keys():
					_count += 1
		return _count


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		i = len(arr) - 1
		cnt = 0
		while i > 1:
			j = i - 1
			k = 0
			while j > k:
				sum = arr[j] + arr[k]
				if sum > arr[i]:
					j = j - 1
				if sum < arr[i]:
					k = k + 1
				if sum == arr[i]:
					cnt = cnt + 1
					j = j - 1
					k = k + 1
			i = i - 1
		return cnt


class Solution:

	def countTriplet(self, arr, n):
		arr.sort()
		ans = 0
		for k in range(n - 1, 1, -1):
			start = 0
			end = k - 1
			while start < end:
				if arr[start] + arr[end] == arr[k]:
					ans += 1
					end -= 1
				elif arr[start] + arr[end] < arr[k]:
					start += 1
				elif arr[start] + arr[end] > arr[k]:
					end -= 1
		return ans


class Solution:

	def countTriplet(self, arr, n):
		sorted_arr = sorted(arr)
		res = 0
		arr_dup = set(sorted_arr)
		for index in range(len(sorted_arr) - 2):
			for index1 in range(index + 1, len(sorted_arr)):
				potentialSum = sorted_arr[index1] + sorted_arr[index]
				if potentialSum in arr_dup:
					res += 1
		return res


class Solution:

	def countTriplet(self, arr, n):
		num_set = set()
		num_triplets = 0
		for i in range(n):
			num_set.add(arr[i])
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] + arr[j] in num_set:
					num_triplets += 1
		return num_triplets


from collections import Counter

class Solution:

	def countTriplet(self, arr, n):
		c = 0
		h = Counter(arr)
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				if arr[i] + arr[j] in h:
					c += 1
		return c


class Solution:

	def countTriplet(self, arr, n):
		d = {}
		index = 0
		triplet = 0
		for x in arr:
			d[x] = index
			index = index + 1
		for i in range(len(arr) - 1):
			for j in range(i + 1, len(arr), 1):
				sum = arr[i] + arr[j]
				if d.get(sum) != None:
					triplet = triplet + 1
		return triplet


class Solution:

	def countTriplet(self, arr, n):
		S = set(arr)
		count = 0
		for i in range(n):
			for j in range(i + 1, n):
				X = arr[i]
				Y = arr[j]
				Sum = X + Y
				if Sum in S:
					count += 1
		return count


class Solution:

	def countTriplet(self, arr, n):
		a = sorted(arr, reverse=True)
		ans = 0
		for i in range(len(a) - 2):
			j = i + 1
			k = len(a) - 1
			while j < k:
				if a[i] == a[j] + a[k]:
					ans += 1
					j += 1
					k -= 1
				elif a[i] < a[j] + a[k]:
					j += 1
				else:
					k -= 1
		return ans


class Solution:

	def countTriplet(self, arr, n):
		count = 0
		arr_dict = {}
		for el in arr:
			arr_dict[el] = 1
		for i in range(0, len(arr) - 1):
			for j in range(i + 1, len(arr)):
				if arr[i] + arr[j] in arr_dict:
					count += 1
		return count