>>107492170
The question obscures some interesting properties which can be exploited, namely that the only spacial property necessary is knowing what numbers are to the left or right of an index and beyond that only the frequency of numbers nums[i]*2 to the left of i and to the right of i need to be know; so the most valuable domain is the frequency domain.
Consider two int arrays
int[] left = new int[100_001];
int[] right = new int[100_001];
Note the upper bound is 100,001 as 0 <= nums[i] <= 100,000.
Fill the right array with the frequencies of every num[i];
for(int i = 0; i < nums.Length; i++)
right[nums[i]]++;
then iterate through nums ordinarily, updating the frequency to the left and right of i, also adding to some running sum the multiple of frequencies of nums[i]*2 to the left and right of i;
long sum = 0;
for(int i = 0; i < nums.Length; i++)
{
int num = nums[i];
right[num]--;
if(num <= 50_000) //Any number above 50,000 doubled exceeds the range of nums[i]
{
int num2 = num * 2;
sum += (long)left[num2] * (long)right[num2];
}
left[num]++; //The left frequency array needs to be updated after the sum, this is only necessary for the special case of 0 where 0 * 2 = 0, so its own frequency is indexed
}
Then mod and return the sum according to the spec;
return (int)(sum % (1_000_000_000 + 7));
The problem is very difficult without knowing that beforehand, but becomes rather simple once you know it. I've found that a good amount of the leetcode questions employ this tactic of being easier in the frequency space, though it's often useless in real problems.
