【Leetcode-1】
一、题目：两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
二、代码：
def twoSum(self, nums: List[int], target: int) -> List[int]: if len(nums) == 0: return [] table = {} for i, v in enumerate(nums): if target - v in table: return [i, table[target-v]] else: table[v] = i return []
【Leetcode-15】
一、题目：三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
二、代码：
def threeSum(self, nums: List[int]) -> List[List[int]]: res = [] if len(nums) == 0: return res nums = sorted(nums) n = len(nums) k = 0 while k < n - 2: if nums[k] > 0:break i, j = k + 1, n - 1 while i < j: s = nums[i] + nums[j] + nums[k] if s == 0: res.append([nums[i], nums[j], nums[k]]) i += 1 j -= 1 while i<j and nums[i-1] == nums[i]: i+= 1 while i<j and nums[j+1] == nums[j]: j-= 1 elif s < 0: # i++ i += 1 while i<j and nums[i-1] == nums[i]: i+= 1 else: j -= 1 while i<j and nums[j+1] == nums[j]: j-= 1 k += 1 while k < n - 2 and nums[k-1] == nums[k]: k += 1 return res
【Leetcode-16】
一、题目：最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
二、代码：
def threeSumClosest(self, nums: List[int], target: int) -> int: """ 双指针确定往哪走,去重 """ res = [float(‘inf‘), -1] # diff和sum nums.sort() n = len(nums) for i in range(n-2): while 0<i<n and nums[i] == nums[i-1]: i += 1 j, k = i+1, n-1 while j < k: total = nums[i] + nums[j] + nums[k] diff = abs(total-target) if total == target: return total if res[0] > diff: res = [diff, total] elif total < target: j += 1 while j < k and nums[j] == nums[j-1]: j += 1 else: k -= 1 while j < k and nums[k] == nums[k+1]: k -= 1 return res[1]
【Leetcode-18】
一、题目：四数之和
二、代码：
def fourSum(self, nums: List[int], target: int) -> List[List[int]]: """ 双指针，去重，剪枝,去重时需要保证该指针不是该指向的第一个元素 """ nums = sorted(nums) n = len(nums) res = [] if n < 4: return res i = 0 while i < n-3: while 0 < i < n and nums[i] == nums[i-1]: i += 1 # 去重 if i >= n-3: break # 剪枝 while i < n-3 and (nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target or nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target): i += 1 # 剪枝 j = i + 1 while j < n-2: while i + 1 < j < n-2 and nums[j] == nums[j-1]: j += 1 # 去重 while j < n-2 and (nums[i] + nums[j] + nums[n-1] + nums[n-2] < target or nums[i] + nums[j] + nums[j+1] + nums[j+2] > target): j += 1 # 剪枝 k, p = j+1, n-1 while k < p: total = nums[i] + nums[j] + nums[k] + nums[p] if total == target: res.append([nums[i], nums[j], nums[k], nums[p]]) k += 1 p -= 1 while j+1 < k < p and nums[k] == nums[k-1]: k += 1 # 去重 while j+1 < k < p and nums[p] == nums[p+1]: p -= 1 # 去重 elif total < target: k += 1 while j+1 < k < p and nums[k] == nums[k-1]: k += 1 # 去重 else: p -= 1 while j+1 < k < p and nums[p] == nums[p+1]: p -= 1 # 去重 j += 1 i += 1 return res
【Leetcode-259】
一、题目：较小的三数之和
给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）
二、代码：
def threeSumSmaller(self, nums: List[int], target: int) -> int: """ 双指针，右指针需要左移时，说明中间一堆都符合条件，左指针需要右移时，中间都不符合，因此左指针左移 """ n = len(nums) nums.sort() res = 0 for i in range(n): j, k = i+1, n-1 while j < k: s = nums[i] + nums[k] + nums[j] if s >= target: # j右移都没用，需要k左移 k -= 1 elif s < target: # k左移的都符合，需要j右移 res += k - j j += 1 return res
原文：https://www.cnblogs.com/EstherLjy/p/14672416.html