[LeetCode题解]开篇!求和问题总结：2Sum/3Sum/4Sum/KSum
[LeetCode题解]开篇!求和问题总结：2Sum/3Sum/4Sum/KSum
前言
之前在美国做访学，日子比较清闲。当时对数据结构和算法几乎一窍不通，便开始在Leetcode上刷算法题，也算是为找工作做准备，经过了一年多，也积累了很多Leetcode题解文章，并在CSDN上开了题解专栏。
算法的重要性我在秋招总结文章中也提到了：算法和数据结构主要是以复习剑指offer和Leetcode原题为主。
在面试中，更多的是考察你的思路。而在线笔试中，就是比拼真刀真枪的码代码比拼了。
我会逐篇解读LeetCode题目，提供解题思路和代码，都是Python或Java实现。
目前规划的题目范围：Leetcode前150题（对于校招，能吃透前150题已经能够满足基本复习需要，之后的题目应该都能做到举一反三了。）
求和问题介绍
求和问题描述(K Sum problem)：
给你一组N个数字(比如 vector num), 然后给你一个目标常数(比如 int target) ，我们的目的是在这一堆数里面找到K个数字，使得这K个数字的和等于target。
K Sum求解方法, 适用2Sum, 3Sum, 4Sum：
- 方法一：暴力，就是枚举所有的K-subset, 那么这样的复杂度就是 从N选出K个，复杂度是O(N^K)，显然不会考察这种方法
- 方法二：双指针，这个算法可以考虑最简单的case, 2sum，这是个经典问题，方法就是先排序，然后利用头尾指针找到两个数使得他们的和等于target，其他Ksum都是同样的思路，只不过要固定前K-2个（利用循环）该方法最容易理解
- 方法三：哈希表 将可能的解存储在hash表中，在数据量很大的时候，去重才能维持很好的效率，不然可能超时。效率高
本文总结了如下几题：
- LeetCode第1题：2Sum
- LeetCode第167题：2Sum II
- LeetCode第15题：3Sum
- LeetCode第16题：3Sum Closest
- LeetCode第18题：4Sum
2Sum：两数之和
https://leetcode-cn.com/problems/two-sum/
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路
方法一：暴力法
思路
暴力法很简单。遍历每个元素 x，并查找是否存在一个值与 target - x相等的目标元素。
复杂度分析：
- 时间复杂度：O(n^2)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)的时间。因此时间复杂度为 O(n^2)
- 空间复杂度：O(1)。
方法二：哈希表
思路
复杂度分析：
- 时间复杂度：O(n)， 我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
- 空间复杂度：O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。
利用字典idxDict保存数字num到其下标idx的映射。遍历查找数字num与目标数target的“互补数”时只需查找idxDict[target - num]是否存在即可。
注意：字典的key是target - num或num都可以
代码
Python：
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
idxDict = dict()
for idx, num in enumerate(nums):
if target - num in idxDict:
return [idxDict[target - num], idx]
idxDict[num] = idx
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
num_dict = {}
for i, num in enumerate(nums):
if num not in num_dict:
num_dict[target - num] = i
else:
return num_dict[num], i
Java：
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
if (map.containsKey(nums[i])) {
return new int[]{map.get(nums[i]), i};
}
map.put(target - nums[i], i);
}
return null;
}
}
Two Sum II：两数之和 II - 输入有序数组
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
题目描述
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
与上面一题唯一的不同就是给的数组是排好序的。
解题思路
方法一：哈希存储
思路
同上
方法二：双指针
思路
时间复杂度：O(nlogn)
用两个变量指向数组的开头和结尾：分别指向nums[0]和nums[numsSize];因为已经进行过排序，如果nums[low]+nums[high] < target，则说明low指向的数太小，需要往后移动；反之，则是high指向的数太大，需要前移，当两者相等，遍历结束 。
代码
Python：
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
nums.sort()
left, right = 0, len(nums) - 1
while left < right:
tmp = nums[left] + nums[right]
if tmp > target:
right -= 1
elif tmp < target:
left += 1
else:
return [left+1, right+1]
Java：
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
int sum;
int left = 0;
int right = len - 1;
while(left < right){
sum = nums[left] + nums[right];
if(sum == target)
return new int[]{left+1, right+1};
else if (sum < target)
left ++;
else
right --;
}
return null;
}
}
3Sum：三数之和
https://leetcode-cn.com/problems/3sum/
题目大意
从一个数组中找到三个数，使这三个数的和为0。有可能存在多组解，也有可能存在重复的解，所以需要去重。比如：num=[-1,0,1,2,-1,-4];那么存在两组解：[[-1,0,1],[-1,-1,2]]，解中的数需要是从小到大排序状态。
解题思路
启发自：博客
- 先将数组排序。
- 排序后，可以按照TwoSum的思路来解题。怎么解呢？可以将num[i]的相反数即-num[i]作为target，然后从i+1到len(num)-1的数组元素中寻找两个数使它们的和为-num[i]就可以了。
- 这个过程要注意去重。
方法一：使用哈希+双指针
思路
这个解法是自己写的，主要是由于直接双指针python过不了，所以用了twosum的哈希解法，然后发现依然超时，因为直接在res这个list上去重还是有很大复杂度，所以只能用dict存储，key为字符串，value为list，最后终于过了，超过91%。 discussion的很多和这个类似
时间复杂度：O(n^2)
代码
class Solution:
def twoSum(self, nums, target):
idxDict = dict()
idx_list = []
for idx, num in enumerate(nums):
if target - num in idxDict:
idx_list.append([idxDict[target - num], idx])
idxDict[num] = idx
return idx_list
def threeSum(self, num):
num.sort()
res = dict()
result = []
for i in range(len(num)-2): # 遍历至倒数第三个，后面两个指针
if (i == 0 or num[i] > num[i-1]) and num[i] <= 0: # 只检索不重复并且目标数（第一个数）小于等于0的情况
left = i + 1;
# right = len(num) - 1
result_idx = self.twoSum(num[left:], -num[i])
for each_idx in result_idx: # 数组后方切片后给twoSum
each_result = [num[i], num[each_idx[0]+(i+1)], num[each_idx[1]+(i+1)]]
if str(each_result) not in res:
res[str(each_result)] = each_result
for value in res.values():
result.append(value)
return result
方法二：双指针
Python：
LeetCode超时
时间复杂度：O(N^2)+O(N) = O(N^2)，但显然比上面一种解法复杂度更高，不然也不会GG。
class Solution:
def threeSum(self, num):
num.sort()
res = []
for i in range(len(num)-2): # 遍历至倒数第三个，后面两个指针
if i == 0 or num[i] > num[i-1]:
left = i + 1
right = len(num) - 1
while left < right: # 值得注意的是，这里左右指针将这个数所有情况都遍历加入，所以遇到同样的数直接跳过
if num[left] + num[right] == -num[i]:
res.append([num[i], num[left], num[right]])
left += 1; right -= 1
while left < right and num[left] == num[left-1]: left +=1
while left < right and num[right] == num[right+1]: right -= 1
elif num[left] + num[right] < -num[i]:
while left < right:
left += 1
if num[left] > num[left-1]: break
else:
while left < right:
right -= 1
if num[right] < num[right+1]: break
return res
Java：
通过，未超市
时间复杂度：O(N^2)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
int i = 0;
while (i < nums.length - 2) {
if (nums[i] > 0) break;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
list.add(Arrays.asList(nums[i], nums[left++], nums[right--]));
while (left < right && nums[left] == nums[left - 1]) ++left;
while (left < right && nums[right] == nums[right + 1]) --right;
} else if (sum < 0) ++left;
else --right; // ++写在前面，说明++先有效，即b要+1，然后赋值给a
}
while (nums[i] == nums[++i] && i < nums.length - 2) ; // 如果数字重复跳过遍历
}
return list;
}
}
3Sum Cloest：最接近的三数之和
https://leetcode-cn.com/problems/3sum-closest/
题目大意
3sum问题的变种，寻找与目标数字最近的那一组数,返回三数之和
解题思路
方法一：双指针
思路
一样的遍历每个数，对剩余数组进行双指针扫描。区别仅仅在于当： sum = A[left] + A[right] (1) sum = target时直接返回 (2) sum != target时，在相应移动left/right指针之前，先计算abs(sum-target)的值，并更新结果。
时间复杂度：O(n log n)（排序）+ O（n^2）= O（n^2）
代码
class Solution:
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort() # 先排序
closest_sum = sys.maxsize
for i in range(len(nums)-2): # 遍历至倒数第三个，后面两个指针
if i == 0 or nums[i] > nums[i-1]: # 排除相同数和刚开始的时候
left = i + 1
right = len(nums) - 1
while left < right:
diff = nums[left] + nums[right] + nums[i] - target
if abs(diff) < abs(closest_sum):
closest_sum = diff
if diff == 0:
return target
elif diff < 0:
left += 1
else:
right -= 1
return closest_sum + target # 原三数之和
4Sum：四数之和
https://leetcode-cn.com/problems/4sum/
题目大意
给出数组，找出四个数组合等于target数
解题思路
方法一：双指针
思路
用双重循环，比3Sum多循环一重，当然最后还是归结到双指针2Sum问题。
代码
双指针（未用dict）
双指针在不用dict的情况下也能通过。
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
resultList = []
nums.sort()
for num1 in range(0, len(nums)-3):
for num2 in range(num1 + 1, len(nums)-2):
num3 = num2 + 1
num4 = len(nums) -1
while num3 != num4:
summer = nums[num1] + nums[num2] + nums[num3] + nums[num4]
if summer == target:
list_temp = [nums[num1],nums[num2],nums[num3],nums[num4]]
if list_temp not in resultList:
resultList.append(list_temp)
num3 += 1
elif summer > target:
num4 -= 1
else:
num3 += 1
return resultList
双指针（用dict）
这里改为dict存储，用空间换时间，结果执行1100ms，比上面的还要多出1000ms，心痛到窒息。
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
resultDict = {}
result = []
nums.sort()
for num1 in range(0, len(nums)-3):
for num2 in range(num1 + 1, len(nums)-2):
num3 = num2 + 1
num4 = len(nums) -1
while num3 != num4:
summer = nums[num1] + nums[num2] + nums[num3] + nums[num4]
if summer == target:
list_temp = [nums[num1],nums[num2],nums[num3],nums[num4]]
list_str = str(list_temp)
if list_str not in resultDict:
resultDict[list_str] = list_temp
num3 += 1
elif summer > target:
num4 -= 1
else:
num3 += 1
for value in resultDict.values():
result.append(value)
return result
方法二：hash表
思路
来自：博客 需要用到哈希表的思路，这样可以空间换时间，以增加空间复杂度的代价来降低时间复杂度。
首先建立一个字典dict，字典的key值为数组中每两个元素的和，每个key对应的value为这两个元素的下标组成的元组，元组不一定是唯一的。
如对于num=[1,2,3,2]来说，dict={3:[(0,1),(0,3)], 4:[(0,2),(1,3)], 5:[(1,2),(2,3)]}。这样就可以检查target-key这个值在不在dict的key值中，如果target-key在dict中并且下标符合要求，那么就找到了这样的一组解。
由于需要去重，这里选用set()类型的数据结构，即无序无重复元素集。最后将每个找出来的解(set()类型)转换成list类型输出即可。
这种思路请参考上述博客，下方均为3Sum变体，不是上述方法的实现
代码
200ms
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
numLen, res, num_dict = len(nums), set(), {}
if numLen < 4:
return []
nums.sort()
for p in range(numLen): # 存储hash表
for q in range(p+1, numLen):
if nums[p]+nums[q] not in num_dict:
num_dict[nums[p]+nums[q]] = [(p,q)]
else:
num_dict[nums[p]+nums[q]].append((p,q))
# print num_dict
for i in range(numLen):
for j in range(i+1, numLen-2):
T = target-nums[i]-nums[j]
if T in num_dict:
for k in num_dict[T]:
if k[0] > j: res.add((nums[i],nums[j],nums[k[0]],nums[k[1]]))
return [list(i) for i in res]
总结
总的来看，求和问题逃不过哈希表和双指针
双指针方法大多需要排序
关注我
我是一名后端开发。主要关注后端开发，数据安全，爬虫等方向。微信：yangzd1102 （请注明来意）
Github：@qqxx6661
个人博客：
- CSDN：@qqxx6661
- 知乎：@Zhendong
- 简书：@蛮三刀把刀
- 掘金：@蛮三刀把刀
原创博客主要内容
- Java知识点复习全手册
- Leetcode算法题解析
- 剑指offer算法题解析
- SpringCloud菜鸟入门实战系列
- SpringBoot菜鸟入门实战系列
- Python爬虫相关技术文章
- 后端开发相关技术文章
个人公众号：Rude3Knife
如果文章对你有帮助，不妨收藏起来并转发给您的朋友们~