我要评论5 四数相加
题目：给定四个包含整数的数组列表 a , b , c , d ,计算有多少个元组 (i, j, k, l) ，使得 a[i] + b[j] + c[k] + d[l] = 0。
核心思路：
- 首先定义一个字典，key放a数组和b数组两数之和，value 放两数之和出现的次数。
- 遍历大a和大b数组，统计两个数组元素之和，和出现的次数，放到字典中。
- 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
- 再遍历大c和大d数组，找到如果 0-(c+d) 在字典中出现过的话，就用count把字典中key对应的value也就是出现次数统计出来。
- 最后返回统计值 count 就可以了
class solution(object):
def foursumcount(self, nums1, nums2, nums3, nums4):
# 初始化一个空字典来存储两个数组元素之和及其出现的次数
numkey = dict()
# 遍历数组nums1中的每一个元素
for num1 in nums1:
# 遍历数组nums2中的每一个元素
for num2 in nums2:
# 计算当前num1和num2的和
sum_12 = num1 + num2
# 如果这个和已经在字典中，增加其计数
if sum_12 in numkey:
numkey[sum_12] += 1
# 如果这个和不在字典中，将其添加到字典中，并设置计数为1
else:
numkey[sum_12] = 1
# 初始化计数器，用于记录满足条件的四元组个数
count = 0
# 遍历数组nums3中的每一个元素
for num3 in nums3:
# 遍历数组nums4中的每一个元素
for num4 in nums4:
# 计算当前num3和num4的和的相反数
sum_34_neg = -num3 - num4
# 如果这个相反数在字典中，说明存在一些num1和num2的和与之相加等于0
# 将这个和出现的次数累加到计数器上
if sum_34_neg in numkey:
count += numkey[sum_34_neg]
# 返回满足条件的四元组个数
return count
6 赎金信
题目：
给你两个字符串：ransomnote 和 magazine ，判断 ransomnote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomnote 中使用一次。
核心思路：
（1）创建一个数组，用数组来实现哈希法，用来存储magazine每一个元素的出现次数。
（2）再遍历ransomnote，将每一个字符对应到哈希数组中，做减法，当出现负数，说明ransomnote中有字符是magazine没有的或者多出的
class solution(object):
def canconstruct(self, ransomnote, magazine):
# 创建一个长度为26的列表，用于记录每个字母出现的次数
# 由于英文字母共有26个，索引0到25分别对应字母a到z
record = [0]*26
# 遍历杂志字符串中的每个字符
for c in magazine:
# 计算当前字符在字母表中的位置，并增加对应的计数
# ord(c) 返回字符c的ascii值，ord('a')是字母a的ascii值
# 这样可以确保字符'a'映射到索引0，'b'映射到索引1，以此类推
record[ord(c) - ord('a')] += 1
# 遍历赎金信字符串中的每个字符
for c in ransomnote:
# 减少对应字母的计数
record[ord(c) - ord('a')] -= 1
# 如果某个字母的计数小于0，说明杂志中的字母不足以组成赎金信
if record[ord(c) - ord('a')] < 0:
return false
# 如果所有字母的计数都不小于0，说明可以用杂志中的字母组成赎金信
return true
7 三数之和
题目：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
核心思路：
-
首先对输入的数组进行排序，这是必要的，因为我们需要利用排序后的特性来使用双指针法。
-
然后代码初始化一个空列表
result，用于存放最终的三元组结果。 -
代码通过一个for循环遍历数组
nums，对于每个元素nums[i]，执行以下步骤：-
如果
nums[i]大于0，由于数组已排序，不可能找到三个数的和为0，因此直接返回result。 -
如果
nums[i]等于前一个元素nums[i-1]，为了避免重复的三元组，使用continue跳过当前的循环迭代。 -
初始化两个指针，
left和right，分别指向当前元素之后的第一个元素和数组的最后一个元素。
-
-
在while循环中，计算当前三个元素的和
sum1：-
如果
sum1大于0，说明和太大了，需要减小，因此将right指针左移。 -
如果
sum1小于0，说明和太小了，需要增大，因此将left指针右移。 -
如果
sum1等于0，找到了一个有效解，将其添加到result列表中，然后移动left和right指针来跳过所有相同的元素，以避免重复解。
-
-
在找到有效解后，通过
left += 1和right -= 1更新left和right指针，以继续寻找下一个可能的解。 -
最后，返回
result列表。
class solution(object):
def threesum(self, nums):
# 对输入的整数数组进行排序
nums.sort()
# 初始化一个空列表用于存放最终的三元组结果
result = []
# 遍历数组中的每一个元素
for i in range(len(nums)):
# 如果当前元素大于0，则不可能找到三个数的和为0，直接返回结果
if nums[i] > 0:
return result
# 如果当前元素与前一个元素相同，为了避免重复的三元组，跳过当前循环
if i > 0 and nums[i] == nums[i-1]:
continue
# 初始化两个指针，left指向当前元素之后的一个元素，right指向数组的最后一个元素
left = i + 1
right = len(nums) - 1
# 当right大于left时，进入循环
while right > left:
# 计算当前三个元素的和
sum1 = nums[i] + nums[left] + nums[right]
# 如果和大于0，说明需要减小和的值，因此将right指针左移
if sum1 > 0:
right -= 1
# 如果和小于0，说明需要增大和的值，因此将left指针右移
elif sum1 < 0:
left += 1
# 如果和等于0，找到了一个有效解，将其添加到结果列表中
else:
result.append([nums[i],nums[left],nums[right]])
# 移动left指针跳过所有相同的元素，以避免重复解
while left < right and nums[left] == nums[left + 1]:
left += 1
# 移动right指针跳过所有相同的元素，以避免重复解
while left < right and nums[right] == nums[right - 1]:
right -= 1
# 移动left和right指针，继续寻找下一个可能的解
left += 1
right -= 1
# 遍历完所有可能的组合后，返回结果列表
return result
8 四数之和
题目：
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
核心思路：
-
首先对输入的数组
nums进行排序，这是必要的，因为我们需要利用排序后的特性来使用双指针法。 -
然后代码初始化一个空列表
result，用于存放最终的四元组结果。 -
代码通过两个嵌套的for循环遍历数组
nums，外层循环的索引为i，内层循环的索引为j。 -
在外层循环中，有两个检查条件：
-
如果
nums[i]大于target且target大于0 且nums[i]大于0，则直接跳出循环，因为后续的数字只会更大，不可能找到和为target的四元组。 -
如果
nums[i]等于前一个元素nums[i-1]，为了避免重复的四元组，使用continue跳过当前的循环迭代。
-
-
在内层循环中，也有两个检查条件：
-
如果
j大于i+1并且nums[j]等于nums[j-1]，为了避免重复的四元组，使用continue跳过当前的循环迭代。 -
如果
nums[j] + nums[i]大于target且target大于0，则跳出内层循环，因为后续的数字只会更大，不可能找到和为target的四元组。
-
-
接下来，初始化两个指针
left和right，分别指向i + 1和n - 1。 -
在while循环中，计算当前四个元素的和
total：-
如果
total大于target，说明和太大了，需要减小，因此将right指针左移。 -
如果
total小于target，说明和太小了，需要增大，因此将left指针右移。 -
如果
total等于target，找到了一个有效解，将其添加到result列表中，然后移动left和right指针来跳过所有相同的元素，以避免重复解。
-
-
最后，返回
result列表。
class solution(object):
def foursum(self, nums, target):
# 对输入的整数数组进行排序
nums.sort()
# 初始化一个空列表用于存放最终的四元组结果
result = []
# 获取数组的长度
n = len(nums)
# 遍历数组中的每一个元素作为第一个加数
for i in range(n):
# 如果当前元素大于目标和且目标和大于0，则不可能找到四个数的和为目标和，直接返回结果
if nums[i] > target and target > 0 and nums[i] > 0:
break
# 如果当前元素与前一个元素相同，为了避免重复的四元组，跳过当前循环
if i > 0 and nums[i] == nums[i-1]:
continue
# 从当前元素的下一个元素开始遍历，作为第二个加数
for j in range(i+1, n):
# 如果当前元素大于第二个加数的位置且与上一个元素相同，为了避免重复的四元组，跳过当前循环
if j > i+1 and nums[j] == nums[j-1]:
continue
# 如果当前元素和第一个加数的和大于目标和且目标和大于0，则不可能找到四个数的和为目标和，跳出内层循环
if nums[j] + nums[i] > target and target > 0:
break
# 初始化两个指针，left指向第二个加数的下一个元素，right指向数组的最后一个元素
left = j + 1
right = n - 1
# 当right大于left时，进入循环
while left < right:
# 计算当前四个元素的和
total = nums[i] + nums[j] + nums[left] + nums[right]
# 如果和大于目标和，说明需要减小和的值，因此将right指针左移
if total > target:
right -= 1
# 如果和小于目标和，说明需要增大和的值，因此将left指针右移
elif total < target:
left += 1
# 如果和等于目标和，找到了一个有效解，将其添加到结果列表中
else:
result.append([nums[i], nums[j], nums[left], nums[right]])
# 移动left指针跳过所有相同的元素，以避免重复解
while right > left and nums[left] == nums[left + 1]:
left += 1
# 移动right指针跳过所有相同的元素，以避免重复解
while right > left and nums[right] == nums[right - 1]:
right -= 1
# 移动left和right指针，继续寻找下一个可能的解
left += 1
right -= 1
# 遍历完所有可能的组合后，返回结果列表
return result
有一些需要注意的地方：
-
内层循环的条件为
for j in range(i+1, n)而不是for j in range(n):，因为我们不需要再从0开始遍历，并且内层循环应该从i+1开始，以避免重复的组合。 -
在内层循环中，这个条件为
if j > i+1 and nums[j] == nums[j-2]而不是if j > i+1 and nums[j] == nums[j-1]，因为我们是在内层循环中检查重复。
发表评论