找人做网站需要注意问题,建设网站公司浩森宇特,邵阳网,什么是网站seo参考文献 代码随想录
一、四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 #xff0c;数组长度都是 n #xff0c;请你计算有多少个元组 (i, j, k, l) 能满足#xff1a;
0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0
示例 1#…参考文献 代码随想录
一、四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l nnums1[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
解法1那当然是暴力枚举了超时 class Solution(object):def fourSumCount(self, nums1, nums2, nums3, nums4)::type nums1: List[int]:type nums2: List[int]:type nums3: List[int]:type nums4: List[int]:rtype: intcount 0# 如果使用的是暴力暴击那么时间复杂度为n的4次方for i in nums1:for j in nums2:for k in nums3:for m in nums4:if i j k m 0:count 1return count解法2在暴力的枚举下我们可以先遍历俩个数组的元素然后求和放到一字典为什么不用数组呢因为当前的元素很大所以使用过字典那么问题来了什么作为key呢value呢题目题目没有说要去重所以我们要统计和相等但是它来自不同数组里的元素那么就把和作为key每个和出现的次数作为value然后我们现在存储的只有2个数组的和对吧那么剩下2个数组的和呢我们可以利用这样一个等式a b c d 0我们不是已经求a b的和吗所以我们就可以使用0 - c d是否在之前出现过如果出现过那么我们的次数是1呢还是value呢答案是value因为题目没有说明要去重而且它们分别来自各个数组里的元素。 class Solution(object):def fourSumCount(self, nums1, nums2, nums3, nums4)::type nums1: List[int]:type nums2: List[int]:type nums3: List[int]:type nums4: List[int]:rtype: inttwoSum {}count 0# 如果使用的是暴力暴击那么时间复杂度为n的4次方for i in nums1:for j in nums2:if (i j) not in twoSum:twoSum[(i j)] 1else:twoSum[(i j)] 1for i in nums3:for j in nums4:if 0 - (i j) in twoSum:count twoSum[0 - (i j)]return count二、赎金信 给你两个字符串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
问题分析假设我们统计了magazine 里每个字母出现的次数为什么我们要统计magazine 而不是ransomNote 呢因为题目已经说明了ransomNote 是否能由magazine构成 所以先遍历magazine 然后遍历ransomNote 的时候做减法因为字符串都是出现的字母都是小写所以我们可以使用数组存储开辟26个空间然后我们有了空间该如何存储呢我们可以利用小写字母对应的数值-‘a’来当做下标value是出现的次数。 class Solution(object):def canConstruct(self, ransomNote, magazine)::type ransomNote: str:type magazine: str:rtype: booldicStr [0] * 26for i in magazine:dicStr[ord(i) - ord(a)] 1for j in ransomNote:dicStr[ord(j) - ord(a)] - 1for i in dicStr:if i 0 :return Falsereturn True 三、三数之和 给你一个整数数组 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 。
问题分析需要a b c 0所以我们可使用一个for循环和一个双指针来代替abca是for循环里的元素然后我们将b 定义成leftc定义成right整么初始化这个两个指针呢因为a是第一个元素那么b就是i的下一个元素那么right就应该为数组最后一个元素的小标在此之前我们的数组必须是排好序的为什么要排序呢因为这样有利于判断a b c是否等于零和移动right和left指针假设a b c 0因为数组已经排好序序了说明right指向的元素大于left为什么不移动a呢因为for循环已经把a值移动了所以我们移动的是right指针那么a b c 0移动left相等就收集结果然后我们该如何对abc去重呢假设a是for循环里的元素我们是判断当前a的下标与a相等呢还是与a下标的前一个相等呢例如[-1, -1, 2]如果你写的a与a对应的下标的下一个元素相等那么是不是把b的取值个去掉了所以只能与前一个数做比较然后bc是在while的是时候去重呢还是在收集结果的时候去重呢例如数组为 [0, 0, 0, 0, 0]这个结果有1种如果是在while的时候去重那么就不会收到结果所以我们要写到收集结果的时候对bc去重如何去重呢我们只需判断各自跟前面是否相等即可 class Solution(object):def threeSum(self, nums)::type nums: List[int]:rtype: List[List[int]]r []nums.sort() # 排序为了移动双指针for i in range(len(nums)):if nums[i] 0: # 那说明后面的元素已经无法小于0了因为nums数组已经排序了升序return r# 对i去重if i 0 and nums[i] nums[i - 1]: # 为什么i0呢因为i是从0开始的continueleft i 1 # i的后一个元素的下标right len(nums) - 1while left right: #注意 这里写 呢还是 呢如果是那么right和left是不是就指向了同一个元素那么总共的元素个数是不是就只有2个了显然不满足题目要求所以是if nums[i] nums[left] nums[right] 0: # 大了要移动right指针为什么不移动left指针呢如果移动left指针有可能会越过结果例如[-1, -2, -2, 8]x相当于你现在是小 小 大如果你移动的是小那么这个小是不是越来越大right - 1elif nums[i] nums[left] nums[right] 0:left 1else:r.append([nums[i], nums[left], nums[right]])while left right and nums[right] nums[right - 1]:right - 1while left right and nums[left] nums[left 1]:left 1right - 1 # 收集了结果要移动双指针left 1return r 四、四数之和 给你一个由 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
你可以按 任意顺序 返回答案 。 示例 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]]
提示
1 nums.length 200-109 nums[i] 109-109 target 109
问题分析和3个数求和类似但是要修改剪枝的条件 class Solution(object):def fourSum(self, nums, target)::type nums: List[int]:type target: int:rtype: List[List[int]]r []nums.sort()for i in range(len(nums)):if nums[i] target and nums[i] 0 and target 0:breakif i 0 and nums[i] nums[i - 1]:continuefor j in range(i 1, len(nums)):if nums[i] nums[j] target and target 0:breakif j i 1 and nums[j] nums[j - 1]:continueleft j 1right len(nums) - 1while left right:s nums[i] nums[j] nums[left] nums[right]if s target:r.append([nums[i], nums[j], nums[left], nums[right]])while left right and nums[left] nums[left1]:left 1while left right and nums[right] nums[right-1]:right - 1left 1right - 1elif s target:left 1else:right - 1return r 总结灵活的替换思维上的一个转化复杂变简单算法结合把一个算法压缩感觉就是多练吧
