##1.Two Sum
-
难度：Medium
-
题目大意：
给定一个整数数组，要求找出数组中两数和为指定数字，返回这两个数的索引。 假定有且只有一个解。 -
思路：
这道题的关键在于如何快速找到 taget-n 的索引，直接扫肯定太慢，当然用哈希表最快。这道题的陷阱在于，注意同一个数不能用两次，需要判断索引是否相同。若同一个数出现多次，记录最后出现的索引位置即可，因为有上面那个判断，可以区分出这个一个数字出现多次的情况。
这种解法的时间复杂度为 O(n)，遍历一次数组，循环中查哈希表复杂度为 1。 -
代码：
class Solution: # @param {integer[]} nums # @param {integer} target # @return {integer[]} def twoSum(self, nums, target): dic={} for i,n in enumerate(nums): dic[n]=i for i,n in enumerate(nums): if target-n in dic and dic[target-n]!=i: return[i,dic[target-n]]
##15.3Sum
-
难度:Medium
-
题目大意：
给定一个整数数组，找出所有能使 a+b+c=0 三元组。注意，元组中按正序排列，不允许重复元组出现。
思路 1：
3 个数和为 0，那么必有以下推断：有 1 个数字 <=0,有 1 个数 >=0。因此，我采用以下解法。先将数组排序（nlogn）,找到 <=0 和 >0 的分界点 dis。第一个数字 firstn 遍历[0,dis),第二个数字 secondn 循环遍历(firstn,len-1),然后在数组（secondn,len-1）中二分查找第三个数字。看似有 2 重循环 + 二分查找，但是由于我们经过了大量的剪枝，所有实际上复杂度没有那么高。 -
代码：
class Solution: # @param {integer[]} nums # @return {integer[][]} def threeSum(self, nums): #print(datetime.datetime.now()) result = [] if len(nums)<3: return result nums.append(1) nums.sort() dis = self.binarySearch(nums,0,len(nums)-1,1) nums.remove(1) for firstn in range(dis): for secondn in range(firstn+1,len(nums)-1): thirdn = self.binarySearch(nums,secondn+1,len(nums)-1,0-(nums[firstn]+nums[secondn])) if thirdn != -1: if[nums[firstn],nums[secondn],nums[thirdn]] not in result: result.append([nums[firstn],nums[secondn],nums[thirdn]]) return result #binary search def binarySearch(self,nums,i,j,n): if n<nums[i] or n>nums[j] or i>j: return -1 mid = (i+j)//2 if n == nums[mid]: return mid elif n < nums[mid]: return self.binarySearch(nums,i,mid-1,n) else: return self.binarySearch(nums,mid+1,j,n) -
思路 2：
这道题作为 2sum 的延伸，当然我们的第一想法应该是上面那么复杂（由于没有系统地训练，这两道题时间间隔比较大）。联系 2sum，我们可以很容易想到使用哈希表，这次哈希表记录的不是数字的索引，而是数字出现的次数，或者说数字可以使用的次数。第一个数字，我们遍历整个数组，同时把选中为第一个数字的哈希值-1.第二个数字，遍历整个数组，需要满足哈希值 >0，把选中的数字的哈希值-1.第三个数字，查找哈希表中满足 0-a-b,且哈希值 >0 的数字。这样复杂度可以降低到(n*n)。 由于没有剪枝，所有两重循环是实打实的。
这里有个奇怪的问题，这份代码提交报了超时，但是超时的用例，使用 leetcode 的测试功能（最近加入的新功能），却能正确得到结果，且时间平均在 80ms，比思路 1 快了 10 倍。 -
代码：
class Solution: # @param {integer[]} nums # @return {integer[][]} def threeSum(self, nums): dic={} result=[] for n in nums: if n not in dic:dic[n]=1 else: dic[n]+=1 for a in nums: dic[a]-=1 for b in nums: if dic[b]>0: dic[b]-=1 if 0-a-b in dic and dic[0-a-b]>0 and sorted([a,b,0-a-b]) not in result: result.append(sorted([a,b,0-a-b])) dic[b]+=1 dic[a]+=1 return result
##16.3Sum Closest
-
难度:Medium
-
题目大意：
给定一个整数数组，求 a,b,c 满足 a+b+c 最接近 target。假设有且仅有 1 个解。 -
思路：
这道题的思路就和 3Sum 比较接近了，遍历前 2 个数字，但是求第三个数字时，需要对二分查找进行修改，在查找不到时返回和该数最接近的数字。 -
代码：
class Solution: # @param {integer[]} nums # @param {integer} target # @return {integer} def threeSumClosest(self, nums, target): sumClosest = 2**32-1 nums.sort() for firstn in range(len(nums)-2): for secondn in range(firstn+1,len(nums)-1): thirdn = self.binarySearch(nums[secondn+1::],0,len(nums[secondn+1::])-1,target-(nums[firstn]+nums[secondn])) stmp = nums[firstn]+nums[secondn]+nums[secondn+1::][thirdn] if stmp == target: return target else: if abs(stmp-target)<abs(sumClosest-target): sumClosest = stmp return sumClosest #binary search #if no such num return the nearlyst def binarySearch(self,nums,i,j,n): if n<nums[i]: if i == 0:return i else: if abs(nums[i]-n)<abs(nums[i-1]-n):return i else:return i-1 if n>nums[j]: if j==len(nums)-1:return j else: if abs(nums[j]-n)<abs(nums[j+1]-n):return j else:return j+1 if i>j: if abs(nums[i]-n)<abs(nums[j]-n):return i else:return j mid = (i+j)//2 if n == nums[mid]:return mid elif n < nums[mid]: return self.binarySearch(nums,i,mid-1,n) else: return self.binarySearch(nums,mid+1,j,n)
##18.4Sum
-
难度:Medium
-
题目大意：
给定整数数组，求出所有 a,b,c,d,满足 a+b+c+d=target。要求元组中升序排列，元组不重复。 -
思路：
若按照 2Sum 和 4Sum 的思路，用 3 重循环遍历前 3 个数，再找到满足要求的第 4 个数，肯定是会超时的（基本上在 OJ 中 3 重循环就肯定会超时了），而且剪枝几乎不可能实现，4 个数可能出现的情况太多。
因此另寻出路：把 4Sum 变成 2 个 2Sum 问题。建立一个哈希表，用于记录｛两数之和:[[索引 a,索引 b],...],...｝,记录索引有一个好处就是可以解决重复数字的问题。遍历 a 和 b,在哈希表中查找 target-a-b，注意排除 1 个数字使用多次的情况。把新的 a+b，加入哈希表中。如此这般时间复杂度仅有（n*n）。 -
代码：
class Solution: # @param {integer[]} nums # @param {integer} target # @return {integer[][]} def fourSum(self, nums, target): result = [] sumdir = {} if len(nums)<4: return result nums.sort() for i in range(len(nums)-1): for j in range(i+1,len(nums)): sumlist = sumdir.get(target - (nums[i]+nums[j])) if sumlist: for na,nb in sumlist: if i not in(na,nb) and j not in(na,nb): tmp = sorted([nums[i],nums[j],nums[na],nums[nb]]) if tmp not in result: result.append(tmp) if not sumdir.get(nums[i]+nums[j]): sumdir[nums[i]+nums[j]] = [] sumdir[nums[i]+nums[j]].append([i,j]) return result
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于