java数据结构与算法刷题-----LeetCode15. 三数之和-拓冰建站

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：`https://blog.csdn.net/grd_java/article/details/123063846`

解题思路

和LeetCode1.两数之和一样，但是这道题边界条件更多。
两数之和那道题目中，我们使用了map进行处理，也讲了如果投机取巧，用大量的数组空间充当map集合，从而达成相同的逻辑处理代码，只是将map换成数组，却比map集合快很多的办法。
这道题也同样可以用map集合，但是因为边界条件过多，代码十分繁琐，尤其是投机取巧用数组充当hash，确实在做题方面，可以达成超越100%的用户，但是没有任何实际意义，只能做题。（后面也会将代码给出）
所以这道题，我会给出比较靠谱的办法，时间复杂度也不高，工作中推荐使用。那就是排序+双指针
先对整个数组排序，然后创建3个指针，从第一个数开始向后枚举
第一个指针 i 只是起到限定第一个数的作用，我们需要通过双指针left和right，来找到第一个数的右边区域的另外两个数
初始left左指针指向第一个数 i 的右边第一个位置，而right指向右边区域末尾，如果3个数相加比0大，就说明right指向的数太大，right–即可，反之，如果相加比0小，left就太小了，进行left++。

代码，时间复杂度O(n^2)，空间复杂度，数组需要排序，工作场景中，不可以改变原数组，因此需要O(n)空间复杂度来排序。然后排序算法使用快速排序，需要O(logN)的栈空间复杂度。

方法一：排序+双指针，效率肯定比不过方法二的hash表，而且使用数组当hash表，但是实际工作中，肯定使用方法一。此方法耗时25ms, 方法二耗时0ms

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);//先排序，为了双指针枚举提供方便List<List<Integer>> ans = new ArrayList<>();//答案需要的链表int n = nums.length;//n代表数组长度for (int i = 0; i < n - 2; ++i) {//因为需要3个数，所以第一个数最多到---倒数第3个int x = nums[i];//x保存当前遍历的第一个数if (i > 0 && x == nums[i - 1]) continue; // 跳过重复数字，枚举过的，就不重复枚举了// 优化一：因为数组排序后是从小到大，如果当前第一个数+它后面两个数，就已经>0了，那当前枚举，包括后面的，都不会符合条件if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化二：如果当前数+倒数那两个数（从小到大排序，也就是末尾的都是最大的）都小于0的话，那也就不用在考虑这个枚举了。肯定枚举不出来if (x + nums[n - 2] + nums[n - 1] < 0) continue; //左右指针int left = i + 1, right = n - 1;while (left < right) {//只要还有元素可以枚举就继续int s = x + nums[left] + nums[right];//3个数的和if (s > 0) --right;//如果s比0大，说明right指向的太大的，right--else if (s < 0) ++left;//如果s比0小，说明left指向太小，left++else {//如果s = 0，说明找到了，添加到链表，然后将继续进行下次枚举ans.add(List.of(x, nums[left], nums[right]));//添加到链表//进行下次枚举之前，我们可以跳过已经枚举过的，也就是和当前left和right数字重复的//因为答案中不要重复的元素for (++left; left < right && nums[left] == nums[left - 1]; ++left); // 跳过重复数字for (--right; right > left && nums[right] == nums[right + 1]; --right); // 跳过重复数字}}}return ans;//返回答案}
}

方法二：使用hash表，用数组充当hash，空间复杂度不确定，取决于数组中存储的值的范围，如果一共有两个元素，[1,999999],那么空间复杂度就是999999. 所以，这是投机取巧的方法，但是做题的效率确实快。只用了0ms

//C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {public List<List<Integer>> threeSum(int[] nums) {return nSum(nums, 3, 0);}public List<List<Integer>> fourSum(int[] nums, int target) {return nSum(nums, 4, target);}public List<List<Integer>> nSum(int[] nums, int k, int target) {return new AbstractList<List<Integer>>() {final List<List<Integer>> res = new ArrayList<>();final List<Integer> path = new ArrayList<>();long min;@Overridepublic List<Integer> get(int index) {init();return res.get(index);}@Overridepublic int size() {init();return res.size();}public void init() {if (res.isEmpty()) {int n = nums.length;long[] Arr = new long[n];Arrays.sort(nums);min = nums[0];for (int i = 0; i < n; i++) {Arr[i] = nums[i] - min;}long NewTarget = (long)target - (long)k * min;C(false, Arr, n, k, NewTarget);}}//C(n, k) = C(n - 1, k) + C(n - 1, k - 1)public void C(boolean T, long[] a, int n, int k, long target) {if (n == 0 || k == 0) {if (target == 0 && k == 0) {res.add(new ArrayList<>(path));}return;}if (k == 2) {if (!T && n != a.length && a[n] == a[n - 1]) {return;}//两数之和模板twoSum(a, 0, n - 1, target);return;}if (n == k) {if (!T && n != a.length && a[n] == a[n - 1]) {return;}//数组中元素和是否等于targetsumArr(a, n, target);return;}if (check(a, n, k, target)) {return;}C(false, a, n - 1, k, target);if (!T && n != a.length && a[n] == a[n - 1]) {return;}if (target - a[n - 1] >= 0) {path.add((int) (a[n - 1] + min));C(true, a, n - 1, k - 1, target - a[n - 1]);path.remove(path.size() - 1);}}void twoSum(long[] a, int l, int r, long target) {if (l >= r || a[r - 1] + a[r] < target || a[l] + a[l + 1] > target) {return;}while (r > l) {long sum = a[l] + a[r];if (sum < target) {l++;} else if (sum > target) {r--;} else {path.add((int) (a[l] + min));path.add((int) (a[r] + min));res.add(new ArrayList<>(path));path.remove(path.size() - 1);path.remove(path.size() - 1);while (r > l && a[l] == a[l + 1]) {l++;}while (r > l && a[r] == a[r - 1]) {r--;}l++;r--;}}}void sumArr(long[] a, int n, long target) {for (int i = n - 1; i > -1; i--) {target -= a[i];path.add((int) (a[i] + min));}if (target == 0) {res.add(new ArrayList<>(path));}for (int i = n - 1; i > -1; i--) {target += a[i];path.remove(path.size() - 1);}}boolean check(long[] a, int n, int k, long target) {if (n - k < 0) {return true;}long max = 0;long min = 0;for (int i = 0; i < k; i++) {min += a[i];max += a[n - i - 1];}if (target < min || target > max) {return true;}return false;}};}
}