1. 前提

leetcode中有多道题是几个数之和，总结一下大致思路。 https://leetcode-cn.com/problems/4sum/submissions/

比如三数之和等于target，四数之和等于target。

最最核心的是两数之和。

2. 两数之和

两数之和的一个好的算法如下：

2.1 对其排序。

可以调用 Arrays.sort()进行排序。

2.2 两指针前后移动找结果

定义指针left和right分别指向第一个元素和最后一个元素的下标。 考察两者之和与target值的比较 若两者之和大，则right左移。（left指向的元素不变，right指向的元素变小，此时值一定变小，可能找到结果） 反之，则left右移 若两者相等，则就是要找的值，可以添加到结果中，同时left++，right–。

2.3 算法复杂度

显然，排序nlog(n)+指针移动距离n，所以总的复杂度为nlog(n).。

3. 多数之和

多数之和的思路如下

3.1 排序

3.2 遍历

对数组进行遍历，将转化为两数之和。而且随着遍历的增加，两数之和的取值范围也减小，复杂度降低。

3.3 事例

四数之和

class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> ans = new ArrayList<>(); if (nums.length < 4) { return ans; } //排序 Arrays.sort(nums); //注：下面这个set是为了保证不出现重复的。 //由于已经是排好序的，添加到set里几个数仍然有序，就可以保证唯一性 Set<List<Integer>> ans1 = new HashSet<>(); for (int i = 0; i < nums.length-3; i++) { //转化为三数问题 for (int j = i+1; j < nums.length-2; j++) { //转化为两数问题 int left = j+1; int right = nums.length-1; int sum = target-nums[i]-nums[j]; while (left < right) { if (nums[left]+nums[right] < sum) { left++; } else if (nums[left] + nums[right] > sum) { right--; } else { List<Integer> list = new ArrayList<>(); list.add(nums[i]); list.add(nums[j]); list.add(nums[left]); list.add(nums[right]); ans1.add(list); left++; right--; } } } } ans.addAll(ans1); return ans; } }