1630.等差子数组

链接：1630.等差子数组
难度：Medium
标签：数组、哈希表、排序
简介：返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... , nums[r[i]] 可以 重新排列 形成 等差数列 ，answer[i] 的值就是 true；否则answer[i] 的值就是 false 。

题解 1 - python

• 编辑时间：2023-03-23
• 执行用时：96ms
• 内存消耗：15MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
        def check(i: int):
            left, right = l[i], r[i]
            size = right-left
            nmax, nmin = max(nums[left:right + 1]), min(nums[left:right+1])
            if (nmax - nmin) % size != 0:
                return False
            elif nmin == nmax:
                return True
            else:
                step = (nmax - nmin) // size
                arr = [False] * (size + 1)
                for i in range(left, right+1):
                    val = (nums[i] - nmin) // step
                    if (nums[i] - nmin) % step != 0 or arr[val]:
                        return False
                    else:
                        arr[val] = True
                return True
        return [check(i) for i in range(len(l))]

题解 2 - rust

• 编辑时间：2023-03-23
• 执行用时：8ms
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn check_arithmetic_subarrays(nums: Vec<i32>, l: Vec<i32>, r: Vec<i32>) -> Vec<bool> {
        let check = |i| -> bool {
            let (left, right) = (l[i] as usize, r[i] as usize);
            let size = right - left;
            let (nmax, nmin) = (*nums[left..=right].iter().max().unwrap(), *nums[left..=right].iter().min().unwrap());
            if (nmax - nmin) % (size as i32) != 0 {
                false
            } else if nmax == nmin {
                true
            } else {
                let step = (nmax - nmin) / (size as i32);
                let mut arr = vec![false; (size + 1) as usize];
                for i in left..=right {
                    let val = ((nums[i] - nmin) / step) as usize;
                    if (nums[i] - nmin) % step != 0 || arr[val] {
                        return false;
                    }
                    arr[val] = true;
                }
                true
            }
        };
        (0..l.len()).map(|i| check(i)).collect::<Vec<bool>>()
    }
}

题解 3 - cpp

• 编辑时间：2023-03-23
• 执行用时：20ms
• 内存消耗：20.2MB
• 编程语言：cpp
• 解法介绍：多次遍历，对每个区间枚举所有值。

class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        vector<bool> res(l.size(), 0);
        for (int i = 0; i < l.size(); i++) {
            int left = l[i], right = r[i], size = right - left,
                nmax = *max_element(nums.begin() + left, nums.begin() + right + 1), 
                nmin = *min_element(nums.begin() + left, nums.begin() + right + 1);
            if ((nmax - nmin) % size != 0) res[i] = false;
            else if (nmin == nmax) res[i] = true;
            else {
                bool f = true;
                int step = (nmax - nmin) / size, list[size + 1];
                memset(list, 0, sizeof(int) * (size + 1));
                for (int i = left; i <= right && f; i++) {
                    int val = (nums[i] - nmin) / step;
                    if ((nums[i] - nmin) % step != 0 || list[val] != 0) f = false;
                    else list[val] = 1;
                }
                res[i] = f;
            }
        }
        return res;
    }
};