[LeetCode/Medium] 1630. Arithmetic Subarrays

1. Input

1) n개의 정수가 담긴 int 배열 nums

2) m개의 인덱스가 담긴 int 배열 l

3) m개의 인덱스가 담긴 int 배열 r

 

2. Output

1) boolean 값을 담은 list output

2) nums를 l[i]부터 r[i]까지 자른 부분 배열이 arithmetic이면 output[i] == true, 아니면 false

3) arithmetic하다는 것은 최소 2개의 원소를 갖고, 각 원소들의 차가 같도록 원소들을 나열할 수 있다는 것이다.

  - {1, 2, 3, 4, 5}는 arithmetic하지만, {1, 2, 3, 5, 6}은 arithmetic하지 않다.

 

3. Constraint

1) n == nums.length

2) m == l.length

3) m == r.length

4) 2 <= n <= 500

5) 1 <= m <= 500

6) 0 <= l[i] < r[i] < n

7) -105 <= nums[i] <= 105

 

4. Example

Input: nums = {4,6,5,9,3,7}, l = {0,0,2}, r = {2,3,5}
Output: {true,false,true}

설명:

  - i=0: l[i]=0. r[i]=2이므로 부분배열={4,6,5} -> {4,5,6}으로 재배열 가능 -> output[i] == true

  - i=1: l[i]=0. r[i]=3이므로 부분배열={4,6,5,9} -> {4,5,6,9}로 재배열해도 안됨 -> output[i] == false

  - i=2: l[i]=2. r[i]=5이므로 부분배열={5,9,3,7} -> {3,5,7,9}로 재배열 가능 -> output[i] == true

 

5. Code

1) 첫 코드(2022/08/19)

List<Boolean> output = new ArrayList();
for(int i=0 ; i<l.length ; i++){
    int[] subarr = new int[r[i]-l[i]+1];
    int index = 0;
    for(int j=l[i] ; j<=r[i] ; j++){
        subarr[index] = nums[j];
        index++;
    }
    Arrays.sort(subarr);
    int dif = subarr[1]-subarr[0];
    boolean b = true;
    for(int j=1 ; j<subarr.length-1 ; j++)
        if(subarr[j+1]-subarr[j]!=dif){
            b = false;
            break;
        }
    output.add(b);
}
return output;

  - 부분 배열을 생성한 후 nums의 값을 넣음

  - 크기 순으로 정렬한 다음, 앞에서부터 비교하면서 차가 같으면 true, 다르면 false를 output에 저장