454. 四数相加 II
【注意】
1.a+b作为key，出现次数作为value，0-(c+d)有没有在map集合里出现过，出现的次数做统计。遍历两个数组时间复杂度为O(n2)。
【代码】
1 class Solution(object): 2 def fourSumCount(self, nums1, nums2, nums3, nums4): 3 """ 4 :type nums1: List[int] 5 :type nums2: List[int] 6 :type nums3: List[int] 7 :type nums4: List[int] 8 :rtype: int 9 """ 10 hashmap = dict() 11 12 for n1 in nums1: 13 for n2 in nums2: 14 if n1 + n2 in hashmap: 15 hashmap[n1+n2] += 1 16 else: 17 hashmap[n1+n2] = 1 18 19 # 0-(c+d)是否出现在hashmap中统计value++ 20 count = 0 21 for n3 in nums3: 22 for n4 in nums4: 23 key = -n3 - n4 24 if key in hashmap: 25 count += hashmap[key] 26 27 return count
383. 赎金信
【注意】
1.采用空间换取时间的哈希策略。
【代码】
1 class Solution(object):
2 def canConstruct(self, ransomNote, magazine):
3 """
4 :type ransomNote: str
5 :type magazine: str
6 :rtype: bool
7 """
8 #方式一.使用数组作为哈希表
9 arr = [0] * 26
10
11 for x in magazine:
12 #记录magazine里各个字符出现的次数
13 arr[ord(x) - ord('a')] += 1
14
15 for x in ransomNote:
16 if arr[ord(x) - ord('a')] == 0:
17 #如果在magazine没有出现过直接返回
18 return False
19 else:
20 arr[ord(x) - ord('a')] -= 1
21
22 return True
23
24 #方式二.defaultdict
25 from collections import defaultdict
26
27 hashmap = defaultdict(int)
28
29 for x in magazine:
30 hashmap[x] += 1
31 for x in ransomNote:
32 value = hashmap.get(x)
33 if value is None or value == 0:
34 return False
35 else:
36 hashmap[x] -= 1
37
38 return True
39
40 #方式三.
41 hashmap = dict()
42
43 for s in ransomNote:
44 if s in hashmap:
45 hashmap[s] += 1
46 else:
47 hashmap[s] = 1
48
49 for l in magazine:
50 if l in hashmap:
51 hashmap[l] -= 1
52
53 for key in hashmap:
54 if hashmap[key] > 0:
55 return False
56
57 return True
58
59 #方式四.
60 c1 = collections.Counter(ransomNote)
61 c2 = collections.Counter(magazine)
62 x = c1 - c2
63
64 if len(x) == 0:
65 return True
66 else:
67 return False
15. 三数之和
【注意】
1.nums[i] == nums[i+1]: 判断的是结果集是否有重复的数。
2.收获一个符合条件的结果，再进行left和right去重。
【代码】
#双指针法
1 class Solution(object): 2 def threeSum(self, nums): 3 """ 4 :type nums: List[int] 5 :rtype: List[List[int]] 6 """ 7 ans = [] 8 n = len(nums) 9 nums.sort() #给数组进行排序 10 11 for i in range(n): #[0,n-1] 12 #排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了 13 if nums[i] > 0: #剪枝操作 14 break 15 left = i + 1 16 right = n - 1 17 if i >= 1 and nums[i] == nums[i-1]: #对a进行去重 18 continue 19 while left < right: #是三元进行求和，所以没有等号 20 sum = nums[i] + nums[left] + nums[right] 21 if sum > 0: 22 right -= 1 23 elif sum < 0: 24 left += 1 25 else: 26 ans.append([nums[i],nums[left],nums[right]]) 27 #去重逻辑应该放在找到一个三元组之后，对b 和 c去重 28 while left != right and nums[left] == nums[left+1]: left += 1 29 while left != right and nums[right] == nums[right-1]: right -= 1 30 left += 1 31 right -= 1 32 33 return ans
18. 四数之和
【注意】
1.四数之和，和三数之和 是一个思路，都是使用双指针法, 基本解法就是在三数之和的基础上再套一层for循环。
2.四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值。
3.三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
【代码】
1 class Solution(object): 2 def fourSum(self, nums, target): 3 """ 4 :type nums: List[int] 5 :type target: int 6 :rtype: List[List[int]] 7 """ 8 #双指针 9 nums.sort() 10 n = len(nums) 11 res = [] 12 13 for i in range(n): 14 if nums[i] > target and nums[i] >= 0: 15 #剪枝操作 16 break 17 if i > 0 and nums[i] == nums[i-1]: 18 #对nums[i]去重 19 continue 20 for k in range(i+1, n): 21 if k > i+1 and nums[k] == nums[k-1]: 22 ##对nums[k]去重 23 continue 24 left = k + 1 25 right = n - 1 26 27 while left < right: 28 if nums[i] + nums[k] + nums[left] + nums[right] > target: 29 right -= 1 30 elif nums[i] + nums[k] + nums[left] + nums[right] < target: 31 left += 1 32 else: 33 res.append([nums[i], nums[k], nums[left], nums[right]]) 34 while left != right and nums[left] == nums [left+1]: left += 1 35 while left != right and nums[right] == nums[right-1]: right -= 1 36 left += 1 37 right -= 1 38 39 return res
标签：四数,15,hashmap,nums,int,随想录,right,return,left From： https://www.cnblogs.com/wuyijia/p/17403833.html