【每日一题】[2441. 与对应负数同时存在的最大正整数]

【每日一题】2441. 与对应负数同时存在的最大正整数

给你一个 不包含 任何零的整数数组 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] <= 1000
• nums[i] != 0

1 双指针

• 首先对数组升序排序
• 设置两个指针，i从前往后、j从后往前
• 如果sum>0，说明已经没有j对应的负数了（i是目前最小的，不会有更小的让sum=0的了），所以j指针应该左移
• 同理sum<0，说明当前i值太小，因此可能存在让目前最大值j加和为0的值，i指针应该右移
• 时间复杂度O(n + logn)，但是双指针比较巧妙没有想到

class Solution {
    public int findMaxK(int[] nums) {
        Arrays.sort(nums);
        var i = 0;
        var j = nums.length - 1;

        while(i < j) {
            var sum = nums[i] + nums[j];
            if(sum > 0) {
                j--;
            } else if(sum < 0) {
                i++;
            } else {
                return nums[j];
            }
        }
        return -1;
    }
}

2 哈希

• 正常想法，O(N)

class Solution {
    public int findMaxK(int[] nums) {
        var len = nums.length;
        var hash = new boolean[2 * 1000 + 1];
        var ans = -1;
        for(var i = 0; i < len; i++) {
            hash[nums[i]+1000] = true;
        }
        for(var i = 0; i < len; i++) {
            var dumy = -nums[i];
            if(hash[dumy+1000]) {
                ans = Math.max(ans, dumy);
            }
        }

        return ans;
    }
}

• 评论区看到的，第一眼没看懂

class Solution {
    public int findMaxK(int[] nums) {
        var len = nums.length;
        var hash = new boolean[2000+1];
        var ans = -1;
        for(var i = 0; i < len; i++) {
            var val = nums[i];
            hash[1000+val] = true;
            if(val < 0 && hash[1000 - val] && -val > ans) {
                ans = Math.max(ans, -val);
            } else if(val > 0 && hash[1000 - val] && val > ans) {
                ans = Math.max(ans, val);
            }
        }
        return ans;
    }
}