2022 Summer SWE Intern Google OA

小亩_0y6bib6 发表于 2021-12-6 15:19
小白提问，怎么搜狗家上海office的面经呀

https://jobs.1point3acres.com/companies/google/interview
我之前是从这里慢慢找的，希望对你有帮助

请问第二题是什么思路？我想先固定和在哈希表计数，但是如果nums[i]很大的话似乎也不行。题目有没有给其他的限制？

1. nums = [10,8,2,1,9]
   
2. import collections
   
3. def most_same_pairs(nums):
   
4.     n = len(nums)
   
5.     s = set()
   
6.     for i in range(n):
   
7.         for j in range(i+1, n):
   
8.             s.add(nums[i] + nums[j])
   
9.     c = collections.Counter(nums)
   
10.     ans = 0
    
11.     nums_set = set(nums)
    
12.     for val in s:
    
13.         cur = 0
    
14.         for num in nums_set:
    
15.             if num*2 > val: break
    
16.             cur += c[val - num] if num != val - num else c[val - num] // 2
    
17.         ans = max(ans, cur)
    
18.     return ans
    
19. most_same_pairs(nums)

复制代码

第二题目前只能想到这么一个O(N^3)的解法，希望有大神给点指导
网上找到一个类似的题，但是有一个不一样的前提条件（输入肯定是[1，n]），能控制在O(N^2)。