longest-subarray-with-restricted-pair-sums

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

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

A subarray <code>nums[l..r]</code> is valid if there are no three distinct indices <code>i</code>, <code>j</code>, and <code>k</code> such that <code>l &lt;= i, j, k &lt;= r</code> and:

<ul>
	<li><code>nums[i] + nums[j] == nums[k]</code></li>
</ul>

Return the maximum length of a valid subarray of <code>nums</code>.

&nbsp;
Example 1:

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

Output: 3

Explanation:

Consider the subarray <code>[3, 5, 3]</code>. The pairs of elements at distinct indices have the following sums:

<ul>
	<li><code>3 + 5 = 8</code></li>
	<li><code>3 + 3 = 6</code>, using the two different occurrences of 3</li>
	<li><code>5 + 3 = 8</code></li>
</ul>

None of these sums is an element at the remaining index, so the subarray is valid.

Every subarray of length 4 contains 2, 3, and 5 at distinct indices, where <code>2 + 3 = 5</code>. Therefore, no longer valid subarray exists, and the answer is 3.
</div>

Example 2:

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

Output: 4

Explanation:

The sums obtained from every pair of elements at distinct indices are 7, 8, 9, 9, 10, and 11. None of these values appears at the remaining index, so the entire array is valid.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 500</code></li>
</ul>