# 1630. Arithmetic Subarrays
###### tags: `Leetcode` `Medium` `Bloomberg` `Arithmetic Sequence`
Link: https://leetcode.com/problems/arithmetic-subarrays/
## 思路
虽然时间复杂度思路一比思路二高，但是跑出来的速度还是思路一比较快
和[1502. Can Make Arithmetic Progression From Sequence](https://hackmd.io/5KsRX2c0T76nSucSfEhf2g)一样的思路
### 思路一 $O(M*NlogN)$ $O(N)$ M是l的长度 N是array的长度
对于每个subarray来说，先copy一份，再sort，看是不是等差数列
### 思路二 $O(M*N)$ $O(N)$
对于每个subarray来说，遍历一遍，找到最大和最小值，将每个数存到set里面，如果最大值和最小值的差不能被元素个数-1整除，那么就return false，接着从最小值开始检查，是不是每个+diff（最大最小值的差除以元素个数-1）的结果都在set里面，如果有一个不在就return false
要注意的是有可能diff = 0，这时候如果set里面只有一个元素，就是true
## Code
### 思路一

class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
         List<Boolean> ans = new ArrayList<>();

	     for(int index = 0; index<l.length; index++){
             boolean arithmetic = false;
	         for(int i=l[index]; i<r[index]; i++){
	             ArrayList<Integer> curr = new ArrayList<>();
	            
	             for(int j=l[index]; j<=r[index]; j++)
	                 curr.add(nums[j]);
	        
	             Collections.sort(curr);
	           
	             int pair = 0;
	             for(int m=0; m<curr.size()-1; m++){
	                int diff = Math.abs(curr.get(0) - curr.get(1));
	                if(Math.abs(curr.get(m) - curr.get(m+1)) != diff)
	                    break;
	                else 
	                    pair++;
	                }
	              
	              if(pair >= curr.size()-1)
	                arithmetic = true;  
                }
	    ans.add(arithmetic);
	    }
        
	    return ans;
    }
}

### 思路二

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(isArithmetic(nums, l[i], r[i]));
        }
        return ans;
    }
    public boolean isArithmetic(int[] nums, int start, int end){
        int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
        Set<Integer> existNum = new HashSet<>();
        for(int i = start;i <= end;i++){
            existNum.add(nums[i]);
            minVal = Math.min(minVal, nums[i]);
            maxVal = Math.max(maxVal, nums[i]);
        }
        int diff;
        if((maxVal-minVal)%(end-start)!=0){
            return false;
        }
        else{
            diff = (maxVal-minVal)/(end-start);
        }
        if(diff == 0){
            if(existNum.size()==1) return true;
            else return false;
        }
        int temp = minVal;
        while(temp<=maxVal){
            if(!existNum.contains(temp)){
                return false;
            }
            temp += diff;
        }
        return true;
    }
}