{"id":7552,"date":"2020-10-24T22:31:32","date_gmt":"2020-10-25T05:31:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7552"},"modified":"2020-10-24T22:35:58","modified_gmt":"2020-10-25T05:35:58","slug":"leetcode-1630-arithmetic-subarrays","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1630-arithmetic-subarrays\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1630. Arithmetic Subarrays"},"content":{"rendered":"\n

A sequence of numbers is called arithmetic<\/strong> if it consists of at least two elements, and the difference between every two consecutive elements is the same. More formally, a sequence s<\/code> is arithmetic if and only if s[i+1] - s[i] == s[1] - s[0] <\/code>for all valid i<\/code>.<\/p>\n\n\n\n

For example, these are arithmetic<\/strong> sequences:<\/p>\n\n\n\n

1, 3, 5, 7, 9\n7, 7, 7, 7\n3, -1, -5, -9<\/pre>\n\n\n\n
The following sequence is not arithmetic<\/strong>:<\/p>\n\n\n\n
1, 1, 2, 5, 7<\/pre>\n\n\n\n
You are given an array of n<\/code> integers, nums<\/code>, and two arrays of m<\/code> integers each, l<\/code> and r<\/code>, representing the m<\/code> range queries, where the ith<\/sup><\/code> query is the range [l[i], r[i]]<\/code>. All the arrays are 0-indexed<\/strong>.<\/p>\n\n\n\n
Return a list of <\/em>boolean<\/code> elements<\/em> answer<\/code>, where<\/em> answer[i]<\/code> is<\/em> true<\/code> if the subarray<\/em> nums[l[i]], nums[l[i]+1], ... , nums[r[i]]<\/code> can be rearranged<\/strong> to form an arithmetic<\/strong> sequence, and<\/em> false<\/code> otherwise.<\/em><\/p>\n\n\n\n
Example 1:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [4,6,5,9,3,7]<\/code>, l = [0,0,2]<\/code>, r = [2,3,5]<\/code>\nOutput:<\/strong> [true,false,true]<\/code>\nExplanation:<\/strong>\nIn the 0th<\/sup> query, the subarray is [4,6,5]. This can be rearranged as [6,5,4], which is an arithmetic sequence.\nIn the 1st<\/sup> query, the subarray is [4,6,5,9]. This cannot be rearranged as an arithmetic sequence.\nIn the 2nd<\/sup> query, the subarray is [5,9,3,7]. This<\/code> can be rearranged as [3,5,7,9]<\/code>, which is an arithmetic sequence.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> 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]\nOutput:<\/strong> [false,true,false,false,true,true]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • n == nums.length<\/code><\/li>
  • m == l.length<\/code><\/li>
  • m == r.length<\/code><\/li>
  • 2 <= n <= 500<\/code><\/li>
  • 1 <= m <= 500<\/code><\/li>
  • 0 <= l[i] < r[i] < n<\/code><\/li>
  • -105<\/sup> <= nums[i] <= 105<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Sort the range of each query and check.<\/p>\n\n\n\n
    Time complexity: O(nlogn * m)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector checkArithmeticSubarrays(vector& nums, vector& l, vector& r) {\n    vector ans(l.size(), true);\n    for (int i = 0; i < l.size(); ++i) {\n      vector arr(begin(nums) + l[i], begin(nums) + r[i] + 1);\n      sort(begin(arr), end(arr));\n      const int d = arr[1] - arr[0];\n      for (int j = 2; j < arr.size() && ans[i]; ++j)\n        ans[i] = ans[i] && (arr[j] - arr[j - 1] == d);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[662,20,177,664,15],"class_list":["post-7552","post","type-post","status-publish","format-standard","hentry","category-array","tag-arithmetic","tag-array","tag-medium","tag-omnlogn","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7552","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7552"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7552\/revisions"}],"predecessor-version":[{"id":7556,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7552\/revisions\/7556"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7552"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7552"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}