1630.等差子数组.md

1630.等差子数组

/*
 * @lc app=leetcode.cn id=1630 lang=typescript
 *
 * [1630] 等差子数组
 */

// @lc code=start
function checkArithmeticSubarrays(nums: number[], l: number[], r: number[]): boolean[] {}
// @lc code=end

解法 1: 枚举

function checkArithmeticSubarrays(nums: number[], l: number[], r: number[]): boolean[] {
  const n = nums.length
  const m = l.length
  const res: boolean[] = new Array(m).fill(false)
  next: for (let k = 0; k < m; k++) {
    const i = l[k]
    const set = new Set([nums[i]])
    let min = nums[i],
      max = nums[i],
      sum = nums[i]
    for (let j = i + 1; j <= r[k]; j++) {
      const num = nums[j]
      if (set.has(num)) {
        if (set.size !== 1) {
          continue next
        }
      }
      set.add(num)
      min = Math.min(min, num)
      max = Math.max(max, num)
      sum += num
    }
    if (set.size === 1) {
      res[k] = true
      continue
    }
    let d = max - min,
      len = r[k] - l[k]
    if (d % len !== 0) continue
    d /= len
    if (((max + min) * (len + 1)) / 2 !== sum) continue
    for (let k = min; k <= max; k += d) {
      if (!set.has(k)) continue next
    }
    res[k] = true
  }
  return res
}

Case

test.each([
  { input: { nums: [4, 6, 5, 9, 3, 7], l: [0, 0, 2], r: [2, 3, 5] }, output: [true, false, true] },
  {
    input: { 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] },
    output: [false, true, false, false, true, true],
  },
])('input: nums = $input.nums, l = $input.l, r = $input.r', ({ input: { nums, l, r }, output }) => {
  expect(checkArithmeticSubarrays(nums, l, r)).toEqual(output)
})