Easy

题目描述

给你一个不含任何零的整数数组 nums，找出其中最大的正整数 k，使得 -k 也在数组中存在。

返回正整数 k。如果不存在这样的整数，返回 -1。

示例 1：

输入：nums = [-1,2,-3,3]
输出：3
解释：3 是数组中唯一有效的 k。

示例 2：

输入：nums = [-1,10,6,7,-7,1]
输出：7
解释：1 和 7 都在数组中有对应的负值。7 的值更大。

示例 3：

输入：nums = [-10,8,6,7,-2,-3]
输出：-1
解释：不存在有效的 k，我们返回 -1。

提示：

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • nums[i] != 0

解题思路

这道题要求找到最大的正整数 k，使得 -k 也在数组中存在。

解法分析：

  1. 哈希表解法：首先将所有数字存入哈希表，然后遍历数组中的每个正数，检查其对应的负数是否存在于哈希表中。记录满足条件的最大正数。

  2. 排序 + 双指针解法：先对数组排序，使用双指针分别指向数组两端。由于排序后负数在左侧，正数在右侧，可以通过移动指针来寻找互为相反数的数对。

  3. 集合解法：类似哈希表，但使用集合来存储数字，逻辑更简洁。

推荐解法： 哈希表解法，时间复杂度最优且代码简洁易懂。

核心思路是利用哈希表的 O(1) 查找特性，遍历所有正数，检查对应负数是否存在，同时维护找到的最大值。

代码实现

class Solution {
public:
    int findMaxK(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int maxK = -1;
        
        for (int num : nums) {
            if (num > 0 && numSet.count(-num)) {
                maxK = max(maxK, num);
            }
        }
        
        return maxK;
    }
};

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_k = -1
        
        for num in nums:
            if num > 0 and -num in num_set:
                max_k = max(max_k, num)
        
        return max_k

public class Solution {
    public int FindMaxK(int[] nums) {
        HashSet<int> numSet = new HashSet<int>(nums);
        int maxK = -1;
        
        foreach (int num in nums) {
            if (num > 0 && numSet.Contains(-num)) {
                maxK = Math.Max(maxK, num);
            }
        }
        
        return maxK;
    }
}

var findMaxK = function(nums) {
    const numSet = new Set(nums);
    let maxK = -1;
    
    for (const num of nums) {
        if (num > 0 && numSet.has(-num)) {
            maxK = Math.max(maxK, num);
        }
    }
    
    return maxK;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表解法
时间复杂度O(n)
空间复杂度O(n)

其中 n 为数组长度。时间复杂度为 O(n) 是因为需要遍历数组两次（一次建立哈希表，一次查找）。空间复杂度为 O(n) 用于存储哈希表。

相关题目