先对数组排序,然后固定一个数字,再求两个数字之和。
public ArrayList<arraylist<integer>> threeSum(int[] num) { //先排序 Arrays.sort(num); ArrayList<arraylist<integer>> res = new ArrayList<>(); int length = num.length; for (int i = 0; i < length - 2; i++) { //过滤掉重复的 if (i != 0 && num[i] == num[i - 1]) continue; int left = i + 1; int right = length - 1; int target = -num[i]; //改为求两数之和 while (left < right) { int midVale = num[left] + num[right]; if (midVale == target) { res.add(new ArrayList<>(Arrays.asList(num[i], num[left], num[right]))); while (left < right && num[left] == num[left + 1])//过滤掉重复的 left++; while (left < right && num[right] == num[right - 1])//过滤掉重复的 right--; left++; right--; } else if (midVale < target) left++; else right--; } } return res; }
截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666