Array
Hash Table
Sorting
Description
A sequence of numbers is called arithmetic if it consists of at least two elements, and the difference between every two consecutive elements is the same. More formally, a sequence s
is arithmetic if and only if s[i+1] - s[i] == s[1] - s[0]
for all valid i
.
For example, these are arithmetic sequences:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic :
1, 1, 2, 5, 7
You are given an array of n
integers, nums
, and two arrays of m
integers each, l
and r
, representing the m
range queries, where the ith
query is the range [l[i], r[i]]
. All the arrays are 0-indexed .
Return a list of boolean
elements answer
, where answer[i]
is true
if the subarray nums[l[i]], nums[l[i]+1], ... , nums[r[i]]
can be rearranged to form an arithmetic sequence, and false
otherwise.
Example 1:
Input: nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]
Output: [true,false,true]
Explanation:
In the 0th query, the subarray is [4,6,5]. This can be rearranged as [6,5,4], which is an arithmetic sequence.
In the 1st query, the subarray is [4,6,5,9]. This cannot be rearranged as an arithmetic sequence.
In the 2nd query, the subarray is [5,9,3,7]. This can be rearranged as [3,5,7,9], which is an arithmetic sequence.
Example 2:
Input: nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]
Output: [false,true,false,false,true,true]
Constraints:
n == nums.length
m == l.length
m == r.length
2 <= n <= 500
1 <= m <= 500
0 <= l[i] < r[i] < n
-105 <= nums[i] <= 105
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust C#
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def checkArithmeticSubarrays (
self , nums : List [ int ], l : List [ int ], r : List [ int ]
) -> List [ bool ]:
def check ( nums , l , r ):
n = r - l + 1
s = set ( nums [ l : l + n ])
a1 , an = min ( nums [ l : l + n ]), max ( nums [ l : l + n ])
d , mod = divmod ( an - a1 , n - 1 )
return mod == 0 and all (( a1 + ( i - 1 ) * d ) in s for i in range ( 1 , n ))
return [ check ( nums , left , right ) for left , right in zip ( l , r )]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
public List < Boolean > checkArithmeticSubarrays ( int [] nums , int [] l , int [] r ) {
List < Boolean > ans = new ArrayList <> ();
for ( int i = 0 ; i < l . length ; ++ i ) {
ans . add ( check ( nums , l [ i ] , r [ i ] ));
}
return ans ;
}
private boolean check ( int [] nums , int l , int r ) {
Set < Integer > s = new HashSet <> ();
int n = r - l + 1 ;
int a1 = 1 << 30 , an = - a1 ;
for ( int i = l ; i <= r ; ++ i ) {
s . add ( nums [ i ] );
a1 = Math . min ( a1 , nums [ i ] );
an = Math . max ( an , nums [ i ] );
}
if (( an - a1 ) % ( n - 1 ) != 0 ) {
return false ;
}
int d = ( an - a1 ) / ( n - 1 );
for ( int i = 1 ; i < n ; ++ i ) {
if ( ! s . contains ( a1 + ( i - 1 ) * d )) {
return false ;
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
public :
vector < bool > checkArithmeticSubarrays ( vector < int >& nums , vector < int >& l , vector < int >& r ) {
vector < bool > ans ;
auto check = []( vector < int >& nums , int l , int r ) {
unordered_set < int > s ;
int n = r - l + 1 ;
int a1 = 1 << 30 , an = - a1 ;
for ( int i = l ; i <= r ; ++ i ) {
s . insert ( nums [ i ]);
a1 = min ( a1 , nums [ i ]);
an = max ( an , nums [ i ]);
}
if (( an - a1 ) % ( n - 1 )) {
return false ;
}
int d = ( an - a1 ) / ( n - 1 );
for ( int i = 1 ; i < n ; ++ i ) {
if ( ! s . count ( a1 + ( i - 1 ) * d )) {
return false ;
}
}
return true ;
};
for ( int i = 0 ; i < l . size (); ++ i ) {
ans . push_back ( check ( nums , l [ i ], r [ i ]));
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 func checkArithmeticSubarrays ( nums [] int , l [] int , r [] int ) ( ans [] bool ) {
check := func ( nums [] int , l , r int ) bool {
s := map [ int ] struct {}{}
n := r - l + 1
a1 , an := 1 << 30 , - ( 1 << 30 )
for _ , x := range nums [ l : r + 1 ] {
s [ x ] = struct {}{}
if a1 > x {
a1 = x
}
if an < x {
an = x
}
}
if ( an - a1 ) % ( n - 1 ) != 0 {
return false
}
d := ( an - a1 ) / ( n - 1 )
for i := 1 ; i < n ; i ++ {
if _ , ok := s [ a1 + ( i - 1 ) * d ]; ! ok {
return false
}
}
return true
}
for i := range l {
ans = append ( ans , check ( nums , l [ i ], r [ i ]))
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 function checkArithmeticSubarrays ( nums : number [], l : number [], r : number []) : boolean [] {
const check = ( nums : number [], l : number , r : number ) : boolean => {
const s = new Set < number > ();
const n = r - l + 1 ;
let a1 = 1 << 30 ;
let an = - a1 ;
for ( let i = l ; i <= r ; ++ i ) {
s . add ( nums [ i ]);
a1 = Math . min ( a1 , nums [ i ]);
an = Math . max ( an , nums [ i ]);
}
if (( an - a1 ) % ( n - 1 ) !== 0 ) {
return false ;
}
const d = Math . floor (( an - a1 ) / ( n - 1 ));
for ( let i = 1 ; i < n ; ++ i ) {
if ( ! s . has ( a1 + ( i - 1 ) * d )) {
return false ;
}
}
return true ;
};
const ans : boolean [] = [];
for ( let i = 0 ; i < l . length ; ++ i ) {
ans . push ( check ( nums , l [ i ], r [ i ]));
}
return ans ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 impl Solution {
pub fn check_arithmetic_subarrays ( nums : Vec < i32 > , l : Vec < i32 > , r : Vec < i32 > ) -> Vec < bool > {
let m = l . len ();
let mut res = vec! [ true ; m ];
for i in 0 .. m {
let mut arr = nums [ l [ i ] as usize ..= r [ i ] as usize ]. to_vec ();
arr . sort ();
for j in 2 .. arr . len () {
if arr [ j - 2 ] - arr [ j - 1 ] != arr [ j - 1 ] - arr [ j ] {
res [ i ] = false ;
break ;
}
}
}
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public bool Check ( int [] arr ) {
Array . Sort ( arr );
int diff = arr [ 1 ] - arr [ 0 ];
for ( int i = 2 ; i < arr . Length ; i ++ ) {
if ( arr [ i ] - arr [ i - 1 ] != diff ) {
return false ;
}
}
return true ;
}
public IList < bool > CheckArithmeticSubarrays ( int [] nums , int [] l , int [] r ) {
List < bool > ans = new List < bool > ();
for ( int i = 0 ; i < l . Length ; i ++ ) {
int [] arr = new int [ r [ i ] - l [ i ] + 1 ];
for ( int j = 0 ; j < arr . Length ; j ++ ) {
arr [ j ] = nums [ l [ i ] + j ];
}
ans . Add ( Check ( arr ));
}
return ans ;
}
}