作者:小迅
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
题意 -> 给定一个无序数据,和两个边界数组,从边界数组中各取一个元素作为左右边界,判断此子数组是否构成等差数列。
直接模拟,题目已经说的非常清楚了,直接遍历边界数组枚举其中的每一个边界,到无序数组取出子数组,判断该数组是否构成等差数列。
由于取出的是无序数组,判断等差数列肯定不好判断,需要对数组进行升序,直接对给定数组进行升序是不行的,因为取子数组时需要原数组的相对顺序。所有可以每次取元素时申请一片内存临时保存并排序即可。
代码注释超级详细
代码
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int cmp(const void *a, const void *b)//排序
{
return *(int *)a - *(int *)b;
}
bool isValue(int *num, int len)//判断是否为等差
{
for (int i = 0; i < len-2; ++i) {
if (num[i+1] - num[i] != num[i+2] - num[i+1]) return false;
}
return true;
}
bool* checkArithmeticSubarrays(int* nums, int numsSize, int* l, int lSize, int* r, int rSize, int* returnSize){
bool *ans = (bool *)malloc(sizeof(bool) * lSize);
int *num;
int len = 0;
for (int i = 0; i < lSize; ++i) {//枚举所有边界
len = r[i] - l[i] + 1;
num = (int *)malloc(sizeof(int) * len);
memcpy(num, nums+l[i], sizeof(int) * len);//初始化子数组
qsort(num, len, sizeof(num[0]), cmp);//排序
ans[i] = isValue(num, len);//判断是否为等差
free(num);
}
*returnSize = lSize;
return ans;
}
作者:小迅
链接:https://leetcode.cn/problems/arithmetic-subarrays/solutions/2185385/mo-ni-zhu-shi-chao-ji-xiang-xi-by-xun-ge-1uq8/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。