leetcode_1. 两数之和
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
解题思路
利用哈希表，在迭代中判断是否存在target-nums[i]这一元素，然后将tmp和其索引存入哈希表中
在python中可以用字典表示哈希表
代码实现
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
ans_map = dict()
for i in range(0, len(nums)): # 一边将列表中的数添加到字典中，一边判断两数之差是否存在于字典中
temp = target - nums[i]
if temp in ans_map: # 判断步骤
return [ans_map[temp], i]
ans_map[nums[i]] = i # 添加步骤（切记先判断再添加，以免key冲突）
注意：此题不适合使用双指针，因为需要先对数组进行排序，而排序后，数组的下标会被打乱，结果要求返回的数字的下标
leetcode_15. 三数之和
题目描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]来源：力扣（LeetCode）
链接：https://dev.lingkou.xyz/problems/3sum
解题思路
- 将数组排序
- 定义指针i,left,right。遍历i,将问题转化为在i之后的数组中寻找nums[i]+nums[left]+nums[right]=0的问题(即三数之和可以使用双指针解决)
- 剪枝，去重
代码实现
# 双指针，所以先固定一个数字，用双指针来找到另外两个数字。注意记得剪枝
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
rnums=[] # 创建一个要返回的新列表
nums.sort() # 排序
n = len(nums)
for i in range(n):
if i > 0 and nums[i] == nums[i-1]: # 避免重复项
continue
if nums[i] > 0:# 减少无关计算，定值大于 0 后，后面的都大于 0，没必要进行计算了
break
left = i + 1
right = n -1
while left < right:
cur_num = nums[i] + nums[left] + nums[right]
if cur_num == 0:
tmp = [nums[i], nums[left], nums[right]]
rnums.append(tmp)
while left < right and nums[left]==nums[left+1]: # 去重
left += 1
while left < right and nums[right]==nums[right-1]: # 去重
right -= 1
left += 1
right -= 1
elif cur_num > 0:
right -= 1
else:
left += 1
return rnums
leetcode_16. 最接近的三数之和
题目描述
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
来源：力扣（LeetCode）
链接：https://dev.lingkou.xyz/problems/3sum-closest
解题思路
- 若数组长度小于3，返回[]
- 排序数组
- 遍历数组
- 跳过重复元素
- 设置左指针left和右指针right，当left < right 时，循环
- get_nums = nums[i] + nums[left] + nums[right]， 如果get_nums = target ,返回target
- 若abs(get_nums - target) < abs(res - target) 说明get_nums更靠近目标，更新res
- 剪枝
- 返回结果
代码实现
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums or len(nums) < 3: # 排除特殊情况
return None
nums.sort()
res = float("inf") # py用来表示正无穷
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]: # 去重，提高效率
continue
left = i + 1
right = len(nums) - 1
while left < right:
get_nums = nums[i] + nums[left] + nums[right]
if get_nums == target:
return target
if abs(get_nums - target) < abs(res - target): # 说明get_nums更靠近目标
res = get_nums # 更新内容
if get_nums - target < 0:
left += 1
else:
right -= 1
return res
leetcode_18. 四数之和
题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
解题思路
- 排序
- 使用双循环固定两个数，用双指针寻找另外两个数，通过比较target大小,移动指针
- 剪枝，去重
代码实现
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
nums.sort()
n = len(nums)
for a in range(n - 3):
# 防止重复
if a > 0 and nums[a] == nums[a - 1]:
continue
# 当最小值和都大于target， 跳出
if nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target:
break
# 数组最大值和小于target, 就遍历下一个
if nums[a] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:
continue
for b in range(a + 1, n - 2):
# 防止重复
if b - a > 1 and nums[b] == nums[b - 1]:
continue
if nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target:
break
if nums[a] + nums[b] + nums[n - 1] + nums[n - 2] < target:
continue
# 双指针
left = b + 1
right = n - 1
while left < right:
tmp = nums[a] + nums[b] + nums[left] + nums[right]
if tmp == target:
res.append([nums[a], nums[b], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif tmp > target:
right -= 1
else:
left += 1
return res
