解题思路
- 暴力解法：最常见，但是效率极低
- hash-map：建立一个hash-map循环遍历一次即可，对应 python的字典
- two-pointers：定位两个指针根据和的大小来移动另外一个。这里设定的指针个数根据题目中K的个数来定。3Sum中可以设定3个指针，固定两个，移动另一个
Leetcode中包含该类型的题目：
| 序号 | 题目 | 难度 |
|---|---|---|
| 1 | Two Sum | easy |
| 167 | Two Sum II-Input array is sorted | easy |
| 15 | 3Sum | medium |
| 16 | 3Sum Closet | medium |
| 259 | 3Sum Smaller | medium |
| 18 | 4Sum | medium |
1、Two Sum
Description：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
Example：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
Solution：
# 使用了哈希表的方法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 建一个字典
dic = {}
# 遍历列表
for i, num in enumerate(nums):
# 如果该值在字典里，返回
if num in dic:
return [i,dic[num]]
# 字典存储target-num的值以及num的索引
dic[target-num] = i
2、Two Sum II-Input array is sorted
Description：
给定一个升序排列的数组和一个target，在数组中找出两个和为target的整数。
返回这两个整数的index，并且要求index1小于index2
注意，index是基于1开始的，也就是说数组的第一个index是1，而不是0
Solution：
# 使用双指针的方法
# 注：该题当然也可以使用哈希表的方法，而且效率几乎一样
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
# 定义左右指针
l = 0; r = len(numbers)-1
while l < r:
# 当两数之和小于target，移动左指针
if numbers[l]+numbers[r] < target:
l += 1
# 当两数之和大于target，移动右指针
elif numbers[l]+numbers[r] > target:
r -= 1
else:
return [l+1, r+1]
3、3Sum
Description：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
Example：
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Solution1：
# 使用双指针从两边向中间遍历的方法。需要先将列表排序
# 和三重循环0(n^3)相比，大大提高效率，时间复杂度是0(n^2)
# 使用not in 判断重复，简便但是效率很低～
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 存储结果列表
result = []
# 首先对nums列表进行排序，无返回值，排序直接改变nums顺序
nums.sort()
for i, item in enumerate(nums):
# 左指针标记i的下一个位置
l = i+1
# 右指针标记最后元素的位置
r = len(nums)-1
while l<r:
temp = nums[i]+nums[l]+nums[r]
# 如果三数之和等于0
if temp == 0:
# 判断是否已经在结果列表内，如果没有添加进来。简单去重操作
if [nums[i], nums[l], nums[r]] not in result:
result.append([nums[i], nums[l], nums[r]])
# 记得移动左右指针
l += 1; r -= 1
# 如果三数之和小于0，只移动左指针
elif temp < 0:
l += 1
# 如果三数之和大于0，只移动右指针
elif temp > 0:
r -= 1
return result
Solution2：
# 去重操作具体到每次遍历、指针移动，大大提高了效率
class Solution2:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
for i, item in enumerate(nums):
# 排序后相邻两数如果相等，则跳出当前循环继续下一次循环
if i>0 and nums[i]==nums[i-1]:continue
l = i+1; r = len(nums)-1
while l<r:
temp = nums[i]+nums[l]+nums[r]
if temp == 0:
result.append([nums[i], nums[l], nums[r]])
l += 1; r -= 1
# 判断l相邻元素是否相等，是的话继续移动
while l<r and nums[l] == nums[l-1]: l += 1
# 判断r相邻元素是否相等，是的话继续移动
while l<r and nums[r] == nums[r+1]: r -= 1
elif temp < 0:
l += 1
elif temp > 0:
r -= 1
return result
4、3Sum Closest
Description：
给定一个整数数组nums和一个target，寻找数组nums中三个整数最接近target，返回这三个数的和。
你可以假定每个输入只有明确的一个解决方案。
Example：
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Solution1：
# 用两个变量记录结果和差值就可以了，比用字典效率更好，而且更好操作
def threeSumClosest(nums, target):
# 将nums排序
nums.sort()
# 定义初始返回值
res = sum(nums[:3])
# 定义初始差值
diff = abs(sum(nums[:3]) - target)
lens = len(nums)
for i in range(lens):
l = i + 1;
r = lens - 1
while l < r:
temp = nums[i] + nums[l] + nums[r]
# 如果三数之和等于target，直接返回
if temp == target: return temp
# 如果现在的差值更小，更新diff和res
if abs(temp - target) < diff:
diff = abs(temp - target)
res = temp
# 如果三数之和小于target，移动左指针
if temp < target:
l += 1
# 如果三数之和大于target，移动右指针
elif temp > target:
r -= 1
return res
网友评论