LeetCode 题解工作台
与对应负数同时存在的最大正整数
给你一个 不包含 任何零的整数数组 nums ，找出自身与对应的负数都在数组中存在的最大正整数 k 。 返回正整数 k ，如果不存在这样的整数，返回 -1 。 示例 1： 输入： nums = [-1,2,-3,3] 输出： 3 解释： 3 是数组中唯一一个满足题目要求的 k 。 示例 2： 输入：…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以用哈希表 记录数组中出现的所有元素，用一个变量 记录满足题目要求的最大正整数，初始时 $ans = -1$。 接下来，我们遍历哈希表 中的每个元素 ，如果 中存在 ，那么我们就更新 $ans = \max(ans, x)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个 不包含 任何零的整数数组 nums ，找出自身与对应的负数都在数组中存在的最大正整数 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] <= 1000nums[i] != 0
解题思路
方法一：哈希表
我们可以用哈希表 记录数组中出现的所有元素，用一个变量 记录满足题目要求的最大正整数，初始时 。
接下来，我们遍历哈希表 中的每个元素 ，如果 中存在 ，那么我们就更新 。
遍历结束后，返回 即可。
时间复杂度 ，空间复杂度 。其中 是数组的长度。
class Solution:
def findMaxK(self, nums: List[int]) -> int:
s = set(nums)
return max((x for x in s if -x in s), default=-1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(m) |
面试官常问的追问
外企场景- question_mark
Understanding of hash table usage and time complexity optimization.
- question_mark
Ability to handle edge cases such as no valid k or arrays with mixed signs.
- question_mark
Clear explanation of scanning and lookups as key components of the solution.
常见陷阱
外企场景- error
Forgetting to account for the case where no valid k exists and returning -1.
- error
Misunderstanding the problem by only focusing on positive integers without checking for the corresponding negative counterpart.
- error
Overcomplicating the solution by using inefficient data structures or algorithms.
进阶变体
外企场景- arrow_right_alt
Consider variations with larger arrays, where the hash set implementation's efficiency becomes crucial.
- arrow_right_alt
Handle input with only negative numbers or only positive numbers.
- arrow_right_alt
Test with an array that has duplicates to see if they affect the output.