526互联

Leetcode刷题day6-哈希表.双指针.三~四数求和.

发布时间 2023-12-06 01:16:28作者: 智障学Leetcode

454.四数相加Ⅱ

454. 四数相加 II - 力扣（LeetCode）
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
    示例 1：
    输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
    输出：2
    解释：
    两个元组如下：
    1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
    2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
    示例 2：
    输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
    输出：1

解题思路：
哈希表：把 $O(n^4)$ 拆分成 $2*O(n^2)$，先遍历nums1和nums2，dict记录所有元素和及其出现的次数，再遍历nums3和nums4，查看所有元素和的反数是否在dict中，若存在则累加元素和出现次数

class Solution():
	def fourSumCount(nums1,nums2,nums3,nums4):
		hashmap = {}
		for i in nums1:
			for j in nums2:
				hashmap[i+j]=hashmap.get(i+j,0)+1
		count = 0
		for i in nums3:
			for j in nums4:
				count += hashmap.get(-(i+j),0)
		return count

383.赎金信

383. 赎金信 - 力扣（LeetCode）
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true

解题思路：
1. 哈希表-列表：生成一个[0]*26列表hashmap，遍历magazine字符串，向列表中存储每个字母重复次数；再遍历ransomNote字符串，累减hashmap中字母次数，若次数小于0，return False
2. 哈希表-字典：生成一个空字典dict，遍历magazine字符串，存储字母及其出现次数；再遍历ransomNote字符串，若当前字母不在dict中 或者 次数<0，return False，否则累减dict中字母次数

class Solution():
	def canConstruct(ransomNote,magazine):  # 哈希表-列表
		hashmap = [0]*26
		for i in magazine:
			hashmap[ord(i)-ord('a')] += 1
		for j in ransomNote:
			hashmap[ord(j)-ord('a')] -= 1
			if hashmap[ord(j)-ord('a')] < 0:
				return False
		return True
			
	def canConstruct(ransomNote,magazine):  # 哈希表-字典
		hashmap = {}
		for i in magazine:
			hashmap[i] = hashmap.get(i,0) + 1
		for j in ransomNote:
			hashmap[j] = hashmap.get(j,0) - 1
			if hashmap[j]<0:
				return False
		return True

15.三数之和

15. 三数之和 - 力扣（LeetCode）
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意：输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释： 唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释： 唯一可能的三元组和为 0 。

解题思路：
1. 哈希表：先求两数之和，并将其存储到hashmap中，再找出剩下一个元素
2. 双指针（三指针）：先对nums排序，再遍历nums，初始index=i，left=i+1，right=len(nums)-1，当left < right时，求和sum=nums[i]+nums[left]+nums[right]，由于nums是有序的，因此sum<0, left右移一位; sum>0, right左移一位; sum=0, 添加元组到最终结果列表, 对左右元素用while去重, 最后left和right分别右移、左移一位

class Solution():
	def threeSum(nums):   # 双指针
		nums = sorted(nums)
		res_tuple = []
		for i in range(len(nums)):
			if nums[i]>0:
				break
			if i>0 and nums[i]==nums[i-1]:
				continue

			left = i+1
			right = len(nums)-1
			while left<right:
				three_sum = nums[i]+nums[left]+nums[right]
				if three_sum>0:
					right-=1
				elif three_sum<0:
					left+=1
				else:
					res_tuple.append([nums[i],nums[left],nums[right]])
					while left<right and nums[right]==nums[right-1]:
						right-=1
					while left<right and nums[left]==nums[left+1]:
						left+=1
					left+=1
					right-=1
		return res_tuple
		
	def threeSum(nums):   # 哈希表
		hashmap = {}  
		whole_list = []  
		for i in range(len(nums)):  
		    for j in range(i + 1, len(nums)):  
		        if nums[i] + nums[j] in hashmap:  
		            hashmap[nums[i] + nums[j]].append([i, j])  
		        else:  
		            hashmap[nums[i] + nums[j]] = [[i, j]]  
		for k in range(len(nums)):  
		    if -nums[k] in hashmap:  
		        temp_list = hashmap[-nums[k]]  
		        for temp in temp_list:  
		            if k not in temp:  
		                whole_list.append(temp + [k])  
		num_lists = []  
		for wl in whole_list:  
		    num_list = []  
		    for s in wl:  
		        num_list += [nums[s]]  
		    num_lists.append(num_list)  
		new_whole_list = list(list(j) for j in set([tuple(sorted(i)) for i in num_lists]))  
		return new_whole_list

18.四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target
    你可以按 任意顺序 返回答案 。
    示例 1：
    输入：nums = [1,0,-1,0,-2,2], target = 0
    输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
    示例 2：
    输入：nums = [2,2,2,2,2], target = 8
    输出：[[2,2,2,2]]

解题思路：
双指针：在三数之和的基础上，多加一层循环

class Solution():
	def fourSum(nums,target):
		nums = sorted(nums)
		res = []
		for i in range(len(nums)):
			if nums[i]>target and target>0 and nums[i]>0: # 要限定target>0
				break
			if i>0 and nums[i]==nums[i-1]:
				 continue
			for j in range(i+1,len(nums)):
				if nums[j]+nums[i]>target and target>0:
					break
				if j>i+1 and nums[j]==nums[j-1]:
					continue
				left,right = j+1,len(nums)-1
				while left<right:
					fsum = nums[i]+nums[j]+nums[left]+nums[right]
					if fsum>target:
						right-=1
					elif fsum<target:
						left+=1
					else:
						res.append([nums[i],nums[j],nums[left],nums[right]])
						while left<right and nums[right]==nums[right-1]:
							right-=1
						while left<right and nums[left]==nums[left+1]:
							left+=1
						left+=1
						right-=1
		return res

应用双指针方法求解的题目：
双指针法将时间复杂度：O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：

链表相关双指针题目：