用 Python 编写程序检查子数组是否可以从等差序列重新排列

pythonserver side programmingprogramming更新于 2025/11/30 10:52:17

假设我们有数字序列 nums，以及另外两个大小为 m 的数组 l 和 r，这两个数组 l 和 r 表示范围查询，如 [l[i], r[i]]。我们必须找到一个布尔序列 ans，其中当子数组 nums[l[i]]、nums[l[i] + 1]、... nums[r[i] - 1]、nums[r[i]] 可以排列以生成等差序列时，ans[i] 为真，否则为假。

如果一个序列至少由两个元素组成，并且每两个连续元素之间的差相同，则称该序列为等差序列。例如，一些算术序列是:[2, 4, 6, 8, 10]、[5, 5, 5, 5]、[4, -2, -8, -14]，但不是 [2, 2, 3, 6, 9]。

因此，如果输入为 nums = [6,8,7,11,5,9]、l = [0,0,2]、r = [2,3,5]，则输出将为 [True, False, True]，因为 −

对于查询 [0, 2]，序列为 [6,8,7]，可以重新排列为 [6,7,8]，这是有效的
对于查询 [0, 3]，序列为 [6,8,7,11]，无法以算术方式重新排列序列
对于查询 [2, 5]，序列为 [7,11,5,9]，可以重新排列为 [5,7,9,11]，这是有效的

为了解决这个问题，我们将遵循以下步骤 −

new := 一个大小与 l 相同的列表，并用所有真值填充
对于范围从 0 到 l - 1 的大小的 i，执行
- 数据 := 从索引 l[i] 到 r[i] 的数字子列表
- 对列表数据进行排序
- d := 一个新列表
- 对于范围从 0 到数据大小 - 2 的 j，执行
  - 在 d 末尾插入 data[j+1] - data[j]
- d := 来自 d 的新集合的新列表
- 如果 d 的大小不等于 1，则
  - new[i] := False
返回 new

示例

让我们看看下面的实现以便更好地理解 −

def solve(nums, l, r):
   new = [True]*len(l)

   for i in range(len(l)):
      data = nums[l[i]:r[i]+1]
      data.sort()

      d = []
      for j in range(len(data) - 1):
         d.append(data[j+1] - data[j])

      d = list(set(d))
      if len(d) != 1:
         new[i] = False
   return new

nums = [6,8,7,11,5,9]
l = [0,0,2]
r = [2,3,5]
print(solve(nums, l, r))