AI summary
type
status
date
slug
summary
category
tags
icon
password
经常刷力扣的读者肯定知道鼎鼎有名的
twoSum 问题，不过除了 twoSum 问题，力扣上面还有 3Sum，4Sum 问题，以后如果想出个 5Sum，6Sum 也不是不可以。总结来说，这类
nSum 问题就是给你输入一个数组 nums 和一个目标和 target，让你从 nums 选择 n 个数，使得这些数字之和为 target。twoSum 问题
1. 两数之和
给定一个整数数组nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。
先排序，然后用双指针。
更优的方法是直接用 hash 表，存储 值-下标 对，然后找
target-x 即可。不过我要继续魔改题目，把这个题目变得更泛化，更困难一点：
nums中可能有多对儿元素之和都等于target，请你的算法返回所有和为target的元素对儿，其中不能出现重复。
比如说输入为
nums = [1,3,1,2,2,3], target = 4，那么算法返回的结果就是：[[1,3],[2,2]]（注意，我要求返回元素，而不是索引）。对于修改后的问题，关键难点是现在可能有多个和为
target 的数对儿，还不能重复，比如上述例子中 [1,3] 和 [3,1] 就算重复，只能算一次。思路还是先排序再双指针，但是要跳过重复元素，碰到重复就再走一步。
这样，一个通用化的
twoSum 函数就写出来了，请确保你理解了该算法的逻辑，我们后面解决 3Sum 和 4Sum 的时候会复用这个函数。这个函数的时间复杂度非常容易看出来，双指针操作的部分虽然有那么多 while 循环，但是时间复杂度还是 O(N)，而排序的时间复杂度是 O(NlogN)，所以这个函数的时间复杂度是 O(NlogN)。
15. 三数之和
给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。注意：答案中不可以包含重复的三元组。
这个问题怎么解决呢？很简单，穷举呗。现在我们想找和为
target 的三个数字，那么对于第一个数字，可能是什么？nums 中的每一个元素 nums[i] 都有可能！那么，确定了第一个数字之后，剩下的两个数字可以是什么呢？其实就是和为
target - nums[i] 的两个数字呗，那不就是 twoSum 函数解决的问题么？时间复杂度为
18. 四数之和
给你一个由n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c和d互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
穷举第一个元素，然后调用上面的 3sum 函数。
和上面一模一样。