参考回答：
2SUM问题
最常见的是2SUM问题（1. 2SUM），就是数组中找出两个数相加和为给定的数。 这道题有两种思路：
- 一种思路从首尾搜索两个数的和，并逐步逼近。
- 另外一种思路是固定一个数A，看SUM-A是否在这个数组之中。
对于第一种思路如下：
此方法是先将数组从小到大排序 设置两个指针，一个指向数组开头，一个指向数组结尾，从两边往中间走。直到扫到满足题意的为止或者两个指针相遇为止。此时这种搜索方法就是类似于杨氏矩阵的搜索方法，就是从杨氏矩阵的左下角开始搜索，直到找到为止。 如果此时题目条件变为如果没有找出最接近的2SUM和问题，解决方法跟上面是一样的 用这种方法2SUM问题的时间复杂度是O(nlogn)O(nlogn)的，主要在于排序的时间。
第二种思路方法如下：
对数组中的每个数建立一个map/hash_map 然后再扫一遍这个数组，判断target-nums[i]是否存在，如果存在则说明有，不存在继续找。当然这样做的话，需要处理一个细节：判重的问题。 代码如下【注意因为题目中说一定有解所以才下面这样写，如果不一定有解，则还要再加一些判断】
vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,vector<int>> mark;for(int i=0;i<nums.size();i++)mark[nums[i]].push_back(i);for(int i = 0;i<nums.size();i++){if(target-nums[i] == nums[i]){if(mark[nums[i]].size() > 1){vector<int> tmp{i,mark[nums[i]][1]};return tmp;}}else{if(mark.find(target-nums[i]) != mark.end()){vector<int> tmp{i,mark[target-nums[i]][0]};return tmp;}}}}
3-SUM 问题
Question: Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.The solution set must not contain duplicate triplets.
根据给定的容量为 n 的整数数组，找到所有满足 a + b + c = 0 的三个元素a、b 、c组合，需去重；
解法
修改问题为：满足 a + b + c = target，target是给定数，原题即 target = 0；
根据题目可知，与 2-SUM 问题类似，在整数数组中不放回的取出三个元素，其和等于给定数（0），不同的是，满足条件的解有多个而且需要去重；
首先想到的解法是，遍历数组，然后调用 2-SUM 问题中的方法寻找两个元素相加等于当前元素的补足，最后执行去重操作；这样的话，查询的时间复杂度是$O(n^2)$，空间复杂度是$O(n^2)$，去重的时间复杂度是$O(n^2)$，空间复杂度是$O(1)$，这绝对不能算一个好方案；
思考其他思路，既然要去重，可以先对数组执行一次排序，这样的话在遍历的时候可以跳过相同元素；在确定一个当前元素后，找另外两个元素相加作为当前元素的补足，此时的解可能是多个的，采用首尾标记的方式可以一次遍历完成查找；
public List<List<Integer>> threeSum(int[] nums, int target){int length = nums.length;List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for(int i = 0; i < length - 2; i++) {if(nums[i] + nums[i+1] + nums[i+2] > target)break; // too largeif(nums[i] + nums[length-1] + nums[length-2] < target)continue; // too smallif(i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1;int right = length - 1;while(left < right){int diff = target - nums[i] - nums[left] - nums[right];if (diff == 0){result.add(new ArrayList<Integer>(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--;left++;right--;}else if (diff > 0){left++;}else {right--;}}}return result;}
