count-special-triplets

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code>.

A special triplet is defined as a triplet of indices <code>(i, j, k)</code> such that:

<ul>
	<li><code>0 &lt;= i &lt; j &lt; k &lt; n</code>, where <code>n = nums.length</code></li>
	<li><code>nums[i] == nums[j] * 2</code></li>
	<li><code>nums[k] == nums[j] * 2</code></li>
</ul>

Return the total number of special triplets in the array.

Since the answer may be large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [6,3,6]

Output: 1

Explanation:

The only special triplet is <code>(i, j, k) = (0, 1, 2)</code>, where:

<ul>
	<li><code>nums[0] = 6</code>, <code>nums[1] = 3</code>, <code>nums[2] = 6</code></li>
	<li><code>nums[0] = nums[1] * 2 = 3 * 2 = 6</code></li>
	<li><code>nums[2] = nums[1] * 2 = 3 * 2 = 6</code></li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: nums = [0,1,0,0]

Output: 1

Explanation:

The only special triplet is <code>(i, j, k) = (0, 2, 3)</code>, where:

<ul>
	<li><code>nums[0] = 0</code>, <code>nums[2] = 0</code>, <code>nums[3] = 0</code></li>
	<li><code>nums[0] = nums[2] * 2 = 0 * 2 = 0</code></li>
	<li><code>nums[3] = nums[2] * 2 = 0 * 2 = 0</code></li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: nums = [8,4,2,8,4]

Output: 2

Explanation:

There are exactly two special triplets:

<ul>
	<li><code>(i, j, k) = (0, 1, 3)</code>

	<ul>
		<li><code>nums[0] = 8</code>, <code>nums[1] = 4</code>, <code>nums[3] = 8</code></li>
		<li><code>nums[0] = nums[1] * 2 = 4 * 2 = 8</code></li>
		<li><code>nums[3] = nums[1] * 2 = 4 * 2 = 8</code></li>
	</ul>
	</li>
	<li><code>(i, j, k) = (1, 2, 4)</code>
	<ul>
		<li><code>nums[1] = 4</code>, <code>nums[2] = 2</code>, <code>nums[4] = 4</code></li>
		<li><code>nums[1] = nums[2] * 2 = 2 * 2 = 4</code></li>
		<li><code>nums[4] = nums[2] * 2 = 2 * 2 = 4</code></li>
	</ul>
	</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= n == nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 105</code></li>
</ul>

第 454 场周赛

weekly-contest-454

specialTriplets

高级工程师

Count Special Triplets

Array

Hash Table

Counting

给你一个整数数组 <code>nums</code>。

特殊三元组 定义为满足以下条件的下标三元组 <code>(i, j, k)</code>：

<ul>
	<li><code>0 &lt;= i &lt; j &lt; k &lt; n</code>，其中 <code>n = nums.length</code></li>
	<li><code>nums[i] == nums[j] * 2</code></li>
	<li><code>nums[k] == nums[j] * 2</code></li>
</ul>

返回数组中&nbsp;特殊三元组&nbsp;的总数。

由于答案可能非常大，请返回结果对 <code>109 + 7</code> 取余数后的值。

&nbsp;

示例 1：

<div class="example-block">
输入： nums = [6,3,6]

输出： 1

解释：

唯一的特殊三元组是 <code>(i, j, k) = (0, 1, 2)</code>，其中：

<ul>
	<li><code>nums[0] = 6</code>, <code>nums[1] = 3</code>, <code>nums[2] = 6</code></li>
	<li><code>nums[0] = nums[1] * 2 = 3 * 2 = 6</code></li>
	<li><code>nums[2] = nums[1] * 2 = 3 * 2 = 6</code></li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： nums = [0,1,0,0]

输出： 1

解释：

唯一的特殊三元组是 <code>(i, j, k) = (0, 2, 3)</code>，其中：

<ul>
	<li><code>nums[0] = 0</code>, <code>nums[2] = 0</code>, <code>nums[3] = 0</code></li>
	<li><code>nums[0] = nums[2] * 2 = 0 * 2 = 0</code></li>
	<li><code>nums[3] = nums[2] * 2 = 0 * 2 = 0</code></li>
</ul>
</div>

示例 3：

<div class="example-block">
输入： nums = [8,4,2,8,4]

输出： 2

解释：

共有两个特殊三元组：

<ul>
	<li><code>(i, j, k) = (0, 1, 3)</code>

	<ul>
		<li><code>nums[0] = 8</code>, <code>nums[1] = 4</code>, <code>nums[3] = 8</code></li>
		<li><code>nums[0] = nums[1] * 2 = 4 * 2 = 8</code></li>
		<li><code>nums[3] = nums[1] * 2 = 4 * 2 = 8</code></li>
	</ul>
	</li>
	<li><code>(i, j, k) = (1, 2, 4)</code>
	<ul>
		<li><code>nums[1] = 4</code>, <code>nums[2] = 2</code>, <code>nums[4] = 4</code></li>
		<li><code>nums[1] = nums[2] * 2 = 2 * 2 = 4</code></li>
		<li><code>nums[4] = nums[2] * 2 = 2 * 2 = 4</code></li>
	</ul>
	</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>3 &lt;= n == nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 105</code></li>
</ul>