首先，我们想一个简单的问题。
Given an array A, find the two numbers a, b in A that makes a * b == 1223.
我们可能首先想这么写
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] * nums[j] == 1223:
return True
但是我们想一下，其实可以优化位O(n), 用一个set就行了
set_ = set(nums)
for num in nums:
if 1223 // num in set_:
return True
然后我们看这个问题
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/#/solutions
实际上就是把上面的过程重复了32遍
class Solution(object):
def findMaximumXOR(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max = 0
for i in range(31, -1, -1):
max <<= 1
prefixes = {num >> i for num in nums}
expect_max = max | 1
for prefix in prefixes: # in prefixes, we want to find the a ^ b == expect_max.
if expect_max ^ prefix in prefixes:
max = expect_max
return max
