We love coding - #1
2023/03/07閱讀時間約 1 分鐘
Hi, I'm coding dog. We love coding.
以下是今天的編碼面試題目。
Q: 給定一個數字列表和一個數字 k，返回列表中是否有任意兩個數字相加得到 k。例如，給定 [10, 15, 3, 7] 和 k 為 17，返回 true，因為 10 + 7 = 17。
加分題：你能在一次遍歷中完成嗎？
A: 為了解決這個問題，我們可以遍歷數字列表並檢查 k 減去當前數字是否在列表中出現。如果存在，則說明我們找到了兩個數字相加得到 k，可以返回 True。否則，我們繼續遍歷直到到達列表的末尾。
以下是實現這個算法的 Python 代碼：
def two_sum(nums, k):num_set = set()for num in nums:if k - num in num_set:return Truenum_set.add(num)return False
在這段代碼中，我們使用一個 set 來存儲我們目前已經看到的數字。我們遍歷數字列表，並對於每個數字，我們檢查 k 減去該數字是否在集合中。如果是，我們已經找到了兩個相加得到 k 的數字，因此返回 True。如果不是，則將該數字添加到集合中並繼續遍歷。如果我們在沒有找到相加得到 k 的數字對的情況下遍歷完列表，則返回 False。
該算法的時間複雜度為 O(n)，其中 n 是列表的長度，因為我們只需要遍歷列表一次。因此，我們可以一次遍歷解決這個問題。
希望這可以幫助您！如果您有任何問題，請讓我知道。
If you like Medium, you can find me (@FangOscar07 ) on Medium.
留言0
查看全部