Medium

题目描述

给你一个整数数组 nums。

如果一对索引 (i, j) 满足以下条件，则称为完美对：

  • i < j
  • 设 a = nums[i], b = nums[j]，则：
    • min(|a - b|, |a + b|) <= min(|a|, |b|)
    • max(|a - b|, |a + b|) >= max(|a|, |b|)

返回不同完美对的数量。

注意：绝对值 |x| 指的是 x 的非负值。

示例 1：

输入：nums = [0,1,2,3]

输出：2

解释：

有 2 个完美对：

(i, j)(a, b)min(|a - b|, |a + b|)min(|a|, |b|)max(|a - b|, |a + b|)max(|a|, |b|)
(1, 2)(1, 2)min(|1 - 2|, |1 + 2|) = 11max(|1 - 2|, |1 + 2|) = 32
(2, 3)(2, 3)min(|2 - 3|, |2 + 3|) = 12max(|2 - 3|, |2 + 3|) = 53

示例 2：

输入：nums = [-3,2,-1,4]

输出：4

示例 3：

输入：nums = [1,10,100,1000]

输出：0

解释：没有完美对，因此答案为 0。

约束条件：

  • 2 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

解题思路

这道题的关键是理解完美对的条件并将其简化。根据题目提示，我们可以将条件化简。

设 x = |a|, y = |b|，不失一般性假设 x <= y。经过数学分析，两个条件可以简化为：y <= 2*x。

证明过程：

  • 当 x <= y 时，min(|a|, |b|) = x，max(|a|, |b|) = y
  • 对于 |a-b| 和 |a+b|，由于绝对值的性质，其最小值总是 <= x
  • 其最大值总是 >= y
  • 因此第一个条件自动满足，第二个条件要求 y <= 2*x

算法步骤：

  1. 按绝对值对数组进行排序，保持原始索引信息以确保 i < j
  2. 使用双指针技术：
    • 外层指针 i 遍历每个位置
    • 内层指针 j 从 i+1 开始，找到所有满足 |nums[j]| <= 2*|nums[i]| 的位置
  3. 对于每个 i，满足条件的 j 的数量就是以 i 为左端点的完美对数量

优化： 由于数组按绝对值排序，当找到第一个不满足条件的 j 时，后续的 j 也不会满足条件，可以提前退出内层循环。

代码实现

class Solution {
public:
    long long perfectPairs(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int, int>> indexed_nums;
        
        // 创建 (绝对值, 原索引) 的配对
        for (int i = 0; i < n; i++) {
            indexed_nums.push_back({abs(nums[i]), i});
        }
        
        // 按绝对值排序
        sort(indexed_nums.begin(), indexed_nums.end());
        
        long long count = 0;
        
        // 双指针
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 确保原索引满足 i < j
                if (indexed_nums[i].second >= indexed_nums[j].second) {
                    continue;
                }
                
                int x = indexed_nums[i].first;
                int y = indexed_nums[j].first;
                
                if (y <= 2 * x) {
                    count++;
                } else {
                    break; // 由于按绝对值排序，后续的y更大，可以退出
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def perfectPairs(self, nums: List[int]) -> int:
        n = len(nums)
        # 创建 (绝对值, 原索引) 的列表
        indexed_nums = [(abs(nums[i]), i) for i in range(n)]
        
        # 按绝对值排序
        indexed_nums.sort()
        
        count = 0
        
        # 双指针
        for i in range(n):
            for j in range(i + 1, n):
                # 确保原索引满足 i < j
                if indexed_nums[i][1] >= indexed_nums[j][1]:
                    continue
                
                x = indexed_nums[i][0]
                y = indexed_nums[j][0]
                
                if y <= 2 * x:
                    count += 1
                else:
                    break  # 由于按绝对值排序，后续的y更大，可以退出
        
        return count

public class Solution {
    public long PerfectPairs(int[] nums) {
        int n = nums.Length;
        var indexedNums = new List<(int abs, int index)>();
        
        // 创建 (绝对值, 原索引) 的列表
        for (int i = 0; i < n; i++) {
            indexedNums.Add((Math.Abs(nums[i]), i));
        }
        
        // 按绝对值排序
        indexedNums.Sort((a, b) => a.abs.CompareTo(b.abs));
        
        long count = 0;
        
        // 双指针
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 确保原索引满足 i < j
                if (indexedNums[i].index >= indexedNums[j].index) {
                    continue;
                }
                
                int x = indexedNums[i].abs;
                int y = indexedNums[j].abs;
                
                if (y <= 2 * x) {
                    count++;
                } else {
                    break; // 由于按绝对值排序，后续的y更大，可以退出
                }
            }
        }
        
        return count;
    }
}

var perfectPairs = function(nums) {
    const n = nums.length;
    // 创建 [绝对值, 原索引] 的数组
    const indexedNums = nums.map((num, i) => [Math.abs(num), i]);
    
    // 按绝对值排序
    indexedNums.sort((a, b) => a[0] - b[0]);
    
    let count = 0;
    
    // 双指针
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            // 确保原索引满足 i < j
            if (indexedNums[i][1] >= indexedNums[j][1]) {
                continue;
            }
            
            const x = indexedNums[i][0];
            const y = indexedNums[j][0];
            
            if (y <= 2 * x) {
                count++;
            } else {
                break; // 由于按绝对值排序，后续的y更大，可以退出
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
排序O(n log n)O(n)
双指针遍历O(n²)O(1)
总体O(n²)O(n)

说明：

  • 时间复杂度：排序需要 O(n log n)，双层循环最坏情况需要 O(n²)，总体为 O(n²)
  • 空间复杂度：需要额外的数组存储索引信息，空间复杂度为 O(n)