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
Solution 1: Hashtable
We can do in one pass by checking whether -x in the hashtable and update ans with abs(x) if so.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int findMaxK(vector<int>& nums) { unordered_set<int> s; int ans = -1; for (int x : nums) { if (abs(x) > ans && s.count(-x)) ans = abs(x); s.insert(x); } return ans; } }; |
Solution 2: Sorting
Sort the array by abs(x) in descending order.
[-1,10,6,7,-7,1] becomes = [-1, 1, 6, -7, 7, 10]
Check whether arr[i] = -arr[i-1].
Time complexity: O(nlogn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int findMaxK(vector<int>& nums) { sort(begin(nums), end(nums), [](int a, int b){ return abs(a) == abs(b) ? a < b : abs(a) > abs(b); }); for (int i = 1; i < nums.size(); ++i) if (nums[i] == -nums[i - 1]) return nums[i]; return -1; } }; |
Solution 3: Two Pointers
Sort the array.
Let sum = nums[i] + nums[j], sum == 0, we find one pair, if sum < 0, ++i else –j.
Time complexity: O(nlogn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int findMaxK(vector<int>& nums) { sort(begin(nums), end(nums)); int ans = -1; for (int i = 0, j = nums.size() - 1; i < j; ) { const int s = nums[i] + nums[j]; if (s == 0) { ans = max(ans, nums[j]); ++i, --j; } else if (s < 0) { ++i; } else { --j; } } return ans; } }; |