化簡無所不在! 用化簡來解 最大的對偶數。Leetcode #2441

Markus Spiske on Unsplash

題目敘述

給定一個非零陣列nums，請找出陣列裡面 最大的對偶數 是誰?

如果無解，請返回-1

對偶數定義: 整數k的對偶數是-k

例如: 99 和 -99互為對偶數。

約束條件

Constraints:

• 1 <= nums.length <= 1000

輸入陣列長度介於 1 ~ 1000 之間。

• -1000 <= nums[i] <= 1000

每個元素值介於 -1000~1000之間。

• nums[i] != 0

每個元素值都不等於0

演算法 化簡到Two-sum

跟著題目、範例思考，可以發現，其實這題就是Two sum兩數之和的變形。

原本兩數之和是在找 x + y = target

這邊特化成，找對偶的 x + (-x) = target = 0 目標值固定是0

基本想法是類似的，依序掃描每個元素，每次看過的數字記錄起來，遇到對偶數 -x的時候，更新對偶數的最大值，最後回傳最大的對偶數，就是答案。

程式碼 化簡到Two-sum

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        
        #記錄看過的數字 
        history = set()
        maxNum = -1
        
        for number in nums:
            
            # 發現對偶數存在    
            if -number in history:
            
                # 更新對偶數的最大值
                maxNum = max( maxNum, abs(number) )

            # 把看過的數字記錄下來
            history.add(number)
            
        return maxNum

複雜度分析

時間複雜度: O(n)

線性掃描，從左到右掃描每個陣列元素，總共耗時O(n)

空間複雜度: O(n)

建立了一個集合，大小最大為元素總數，所占空間為O(n)

關鍵知識點

尋找對偶數，相當於找兩數之和 x + y = 0, 且 y = -x

也可以說就是在找 x + (-x) = 0，並且找出所有解集合裡面x的最大值。

可以回去複習兩數之和這題，兩題考的其實是同一個觀念。

Reference:

[1] Largest Positive Integer That Exists With Its Negative - LeetCode