two sum变形题挑战一下吧皮卡丘

timzyt

本帖最后由 timzyt 于 2021-7-31 22:52 编辑

def twoSumUniq(arr, target):
import collections
dic = collections.defaultdict(int)
ans = []
for n in arr:
if n not in dic:
# if n does not exist in dic before
# we just treat it as normal 2-sum
if target - n in dic:
ans.append([n, target - n])
elif dic[n] == 1:
# if n exists once in dic, and we meet n again
# we consider 2*n == target situation
if n * 2 == target:
ans.append([n, n])
dic[n] += 1
return ans

复制代码

可以定义一个hashtable: <number, freq of the number in array>
然后扫描数组，分类讨论2种情况。
1. n之前不存在hashtable中，这是最简单的情况，就把它当作普通2-sum来做
2. n存在hashtable中一次，这是corner case：考虑2n=target的情况
3. n存在hashtable中多次，这种情况跳过，因为再计算就重复了！

楼主可以看看这道类似的题目！https://www.lintcode.com/problem/587/

欢迎讨论！

ewajwtewg

class Solution:
def twoSum(nums, target):
l, r = 0, len(nums)-1
ans = []
while l < r:
if nums[l] + nums[r] < target:
l += 1
elif nums[l] + nums[r] > target:
r -= 1
else:
ans.append([nums[l],nums[r]])
repeat = nums[l]
while nums[l] == repeat:
l += 1
repeat = nums[r]
while nums[r] == repeat:
r -= 1
return ans
nums = [1, 2, 2, 3, 3, 4, 4, 5]
target = 6
print(twoSum(nums,target))

复制代码

ewajwtewg

class Solution:
def twoSum(nums, target):
l, r = 0, len(nums)-1
ans = []
while l < r:
if nums[l] + nums[r] < target:
l += 1
elif nums[l] + nums[r] > target:
r -= 1
else:
ans.append([nums[l],nums[r]])
repeat = nums[l]
while nums[l] == repeat:
l += 1
repeat = nums[r]
while nums[r] == repeat:
r -= 1
return ans
nums = [1, 2, 2, 3, 3, 4, 4, 5]
target = 6
print(twoSum(nums,target))

复制代码

kkrrt

hashmap- key 存 num里的数字 value 存频率，然后按普通2 sum来做。找到一组之后就把用了的数字从hashmap里移调。当遇到 target-n == n的时候判断一下n 的频率是否是大于等于2的只有大于等于2才说明nums里有足够的数

[Leetcode] two sum变形题挑战一下吧皮卡丘