代码随想录二刷(哈希表)

三数之和思路反正对于我来说是真的难想出来。
在这里插入图片描述
若这道题还是采用哈希表的思路去做，非常麻烦，并且还要考虑去重的操作。所以这道题其实用双指针，是更方便的。

具体程序如下：

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

下面来看下四数之和：
在这里插入图片描述
四数之和相当于三数之和升级了一下，并且target不是0了。按照三数之和的思路，再加一个变量作为外层循环。组合出来四个数即可。

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:result = []n = len(nums)nums.sort()for i in range(n):if nums[i] > target and target > 0:break if i > 0 and nums[i] == nums[i-1]:continuefor j in range(i+1,n):if (nums[i] + nums[j]) > target and target > 0:break if j > i + 1 and nums[j] == nums[j-1]:continueleft = j + 1right = n - 1while right > left:sum = nums[i] + nums[j] + nums[left] + nums[right]if sum > target:right -= 1elif sum < target:left += 1else:result.append([nums[i],nums[j],nums[left],nums[right]])while right > left and nums[right] == nums[right-1]:right -= 1while right > left and nums[left] == nums[left+1]:left += 1right -= 1left += 1return result