[LeetCode] 1630. Arithmetic Subarrays

https://leetcode.com/problems/arithmetic-subarrays/description/

Arithmetic Subarrays - LeetCode

leetcode - Arithmetic Subarrays

문제 유형 : 배열, 정렬, 수학

문제 난이도 : Medium

 

 

문제

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.

 

숫자들의 배열에서 두 연이은 요소들의 차가 일정한 요소들로 이루어져있으면 산술적인 배열이라고 부를 수 있다.

n개의 정수배열 nums가 있다.

그리고 정수 배열 l과 r배열이 m개의 길이로 주어진다.

 

nums의 l[i]번째부터 r[i]번째까지 의 요소로 부분배열을 만들어서 재배열 했을 때 산술적인 배열이라고 볼 수 있는지에 대한 여부를 배열에 담아 반환하시오.

 

 

풀이

각 l부터 r마다 인덱스를 뽑아서 nums의 부분배열을 만들어준 다음, 그 부분배열이 산술배열인지 검증하면 된다.

 

산술배열인지 검증하는 방법은 정렬을 한 후, i번째 요소를 두 배 한게 i-1번째와 i+1번째를 합한 값과 같은지를 보면 된다.

(arr[i] - arr[i-1] = arr[i+1] - arr[i]를 정리하면 arr[i] * 2 =arr[i-1] + arr[i+1], i는 1부터 부분배열의 길이-2까지의 인덱스)

각각 검증한 논리값들을 따로 배열에 담고, m번 반복하면 된다.

 

 

코드

C++

class Solution {
public:
    bool isArithmetic(vector<int> &arr) {
        for(int i = 1; i < arr.size()-1; i++) {
            if(arr[i] * 2 != arr[i-1] + arr[i+1]) return false;
        }

        return true;
    }

    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        vector<bool>table;
        const int m = l.size();
        for(int i = 0; i < m; i++) {
            vector<int> subarr;
            for(int j = l[i]; j <= r[i]; j++) {
                subarr.push_back(nums[j]);
            }
            sort(subarr.begin(), subarr.end());
            table.push_back(isArithmetic(subarr));
        }

        return table;
    }
};