[LeetCode] 2441. Largest Positive Integer That Exists With Its Negative

CNoodle / 2023-05-13 / 原文

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

Example 1:

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the only valid k we can find in the array.

Example 2:

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3:

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no a single valid k, we return -1.

Constraints:

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

与对应负数同时存在的最大正整数。

给你一个不包含任何零的整数数组 nums ，找出自身与对应的负数都在数组中存在的最大正整数 k 。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/largest-positive-integer-that-exists-with-its-negative
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是 hashset。我们需要遍历 input 数组两遍，第一遍我们将所有元素都放入 hashset；第二遍遍历的时候，对于每个遇到的数字 num（有可能是负数），我们需要检查 hashset是否同时存在 -num，如果存在，则 Math.abs(num) 有可能是要找的目标值。注意最后有可能是找不到的，我们要返回 -1。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int findMaxK(int[] nums) {
 3         Set<Integer> set = new HashSet<>();
 4         for (int num : nums) {
 5             set.add(num);
 6         }
 7         
 8         int res = -1;
 9         for (int num : nums) {
10             if (set.contains(num) && set.contains(-num)) {
11                 res = Math.max(res, Math.abs(num));
12             }
13         }
14         return res;
15     }
16 }