算法训练第七天

454. 四数相加 II

思路：

这道题如果用暴搜的方式去做的话，时间复杂度为O(N^{4)，一定会超时。我们可以使用哈希表的方式记录每个值出现的次数，如果我们使用两数相加的思路，遍历前三个数组的和res，然后在第四个数组中寻找0-res，leetcode给出的时间复杂度为*O*(N}2logN)，也会超时。此时可以使用两两组合的方式，前两个数组为一组，后两个数组为一组，遍历两组的和，可以将该问题转化为“两数相加”。此时时间复杂度为O(N^2)。

代码：

def fourSumCount(self, nums1, nums2, nums3, nums4):""":type nums1: List[int]:type nums2: List[int]:type nums3: List[int]:type nums4: List[int]:rtype: int"""ans = 0di1 = {}for i in nums1:for j in nums2:res = i+jif di1.get(res):di1[res]+=1else:di1[res] = 1for k in nums3:for l in nums4:res = k+lif di1.get(0-res,None):ans = ans+di1.get(0-res,None)return ans

383. 赎金信

思路：

这道题其实就是一道散列表算法的经典应用，开一个散列表记录magazine出现的字符，ransomNote每出现一个词，就去散列表查找，如果没找到，直接返回False，如果找到了，但是value已经被用完了，也返回False，如果找到了但是value大于0，那么就让value减一。

代码：

class Solution(object):def canConstruct(self, ransomNote, magazine):""":type ransomNote: str:type magazine: str:rtype: bool"""di = {}for i in magazine:if di.get(i):di[i]+=1else:di[i] = 1for i in ransomNote:if di.get(i,None) is None:return Falseelif di.get(i)==0:return Falseelse:di[i]-=1return True

15. 三数之和

思路：

梦碎的地方。双指针算法，遍历i指针，left指向i+1，right指向数组末尾。

代码：

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort()ans = []for i in range(len(nums)-2):if i>0 and nums[i]==nums[i-1]:continueleft = i+1right = len(nums)-1while left<right:if (nums[i]+nums[left]+nums[right])>0:right-=1elif (nums[i]+nums[left]+nums[right])<0:left+=1else:ans.append([nums[i],nums[left],nums[right]])left+=1while left<right and nums[left]==nums[left-1]:left+=1right-=1while left<right and nums[right]==nums[right+1]:right-=1return ans

18. 四数之和

思路：

相当于在三数之和后面多了一层循环

代码：

class Solution(object):def fourSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[List[int]]"""nums.sort()ans = []for k in range(0,len(nums)-3):if k>0 and nums[k]==nums[k-1]:continuefor i in range(k+1,len(nums)-2):if i>k+1 and nums[i]==nums[i-1]:continueleft = i+1right = len(nums)-1while left<right:if (nums[k]+nums[i]+nums[left]+nums[right])>target:right-=1elif (nums[k]+nums[i]+nums[left]+nums[right])<target:left+=1else:ans.append([nums[k],nums[i],nums[left],nums[right]])left+=1while left<right and nums[left]==nums[left-1]:left+=1right-=1while left<right and nums[right]==nums[right+1]:right-=1return ans