Easy

题目描述

给你一个只包含 0、1 和 2 的整数数组 nums。

如果 nums[i] == 1 且 nums[j] == 2，则称一对索引 (i, j) 为有效的。

返回所有有效对中 i 和 j 之间的最小绝对差。如果不存在有效对，返回 -1。

索引 i 和 j 之间的绝对差定义为 abs(i - j)。

示例 1：

输入：nums = [1,0,0,2,0,1]
输出：2
解释：
有效对为：
- (0, 3) 绝对差为 abs(0 - 3) = 3
- (5, 3) 绝对差为 abs(5 - 3) = 2
因此，答案是 2。

示例 2：

输入：nums = [1,0,1,0]
输出：-1
解释：
数组中没有有效对，因此答案是 -1。

约束条件：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 2

解题思路

解题思路

这是一道简单的数组遍历问题，需要找到所有满足条件的索引对并求出最小绝对差。

方法一：暴力枚举（推荐） 由于题目约束 n ≤ 100，可以直接使用双重循环暴力枚举所有可能的索引对 (i, j)。对于每一对索引，检查是否满足 nums[i] == 1 且 nums[j] == 2 的条件，如果满足则计算绝对差并更新最小值。

方法二：预处理优化 可以先遍历一遍数组，分别记录所有值为 1 和值为 2 的索引位置，然后对这两个索引列表进行双重遍历。虽然时间复杂度相同，但在实际执行中可能会稍快一些。

由于数据规模较小，两种方法的性能差异不大，这里采用更直观的暴力枚举方法。

算法步骤：

  1. 初始化最小差值为一个较大的值（如 INT_MAX）
  2. 双重循环遍历所有索引对 (i, j)
  3. 检查是否为有效对：nums[i] == 1 && nums[j] == 2
  4. 如果是有效对，计算 abs(i - j) 并更新最小值
  5. 如果找到了有效对，返回最小差值；否则返回 -1

代码实现

class Solution {
public:
    int minAbsoluteDifference(vector<int>& nums) {
        int minDiff = INT_MAX;
        bool found = false;
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (nums[i] == 1 && nums[j] == 2) {
                    found = true;
                    minDiff = min(minDiff, abs(i - j));
                }
            }
        }
        
        return found ? minDiff : -1;
    }
};

class Solution:
    def minAbsoluteDifference(self, nums: list[int]) -> int:
        min_diff = float('inf')
        found = False
        
        for i in range(len(nums)):
            for j in range(len(nums)):
                if nums[i] == 1 and nums[j] == 2:
                    found = True
                    min_diff = min(min_diff, abs(i - j))
        
        return min_diff if found else -1

public class Solution {
    public int MinAbsoluteDifference(int[] nums) {
        int minDiff = int.MaxValue;
        bool found = false;
        
        for (int i = 0; i < nums.Length; i++) {
            for (int j = 0; j < nums.Length; j++) {
                if (nums[i] == 1 && nums[j] == 2) {
                    found = true;
                    minDiff = Math.Min(minDiff, Math.Abs(i - j));
                }
            }
        }
        
        return found ? minDiff : -1;
    }
}

var minAbsoluteDifference = function(nums) {
    let minDiff = Infinity;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {
            for (let j = 0; j < nums.length; j++) {
                if (nums[j] === 2) {
                    minDiff = Math.min(minDiff, Math.abs(i - j));
                }
            }
        }
    }
    
    return minDiff === Infinity ? -1 : minDiff;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 需要双重循环遍历所有索引对
空间复杂度O(1) - 只使用常数额外空间