n数之和
type
status
date
slug
summary
tags
category
icon
password
Blocking
Blocked by
top
URL
Sub-item
Parent item
总结：先进行排序（为了去重），然后采用分治法，通过循环递归将 n 个数拆解 n-1 的子问题。直到规模减少到 2，然后再直接调用求两数之和的函数，从而得到最终结果。
n数之和是一个经典的问题。给定一个整数数组和一个目标值，找到数组中n个数的和，使它们的和与目标值相等。如果存在这样的三元组，请输出它们的下标；否则，返回一个空列表。
两数之和
假设给定以下数组和目标和：
哈希表法
以下是使用哈希表法实现的查找函数代码：
代码实现
双指针法
以下是使用双指针法实现的查找函数代码：
代码实现
重复的两数之和
现在难度增加，数组中会出现重复的子元素。
关键难点是现在可能有多个和为
target 的数对，比如上述例子中 [1,3] 和 [3,1]就算重复，只能算一次。哈希表法（不推荐）
哈希表法很难去重，需要在结果里进行重复查找，性能很差，所以不推荐。
双指针法
对于n数之和问题中存在重复的情况，可以使用双指针法+剪枝。
- 先对数组进行排序。
- 然后在查找过程中，如果当前元素与前一个元素相同，则跳过该元素，以避免重复。
时间复杂度：
- 排序复杂度：
O(NlogN)
- 循环复杂度：
O(N)
所以总体时间复杂度是
O(NlogN)
具体实现代码如下：
代码实现
多数之和
基本思路：
- 穷举，先排序（为了去重），然后循环每个元素，作为第一个数字，直到求两个数字时用
twoSum函数查找。
- 同时需要注意为了不让第一个数重复，每次循环前要判断是否与前一个数字相同。