611.有效三角形的个数
题目：
给定一个包含非负整数的数组
nums，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3示例 2:
输入: nums = [4,2,3,4] 输出: 4提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
思路：这个题目就是想让我们在给的数组中找出可以组成三角形的个数。确定三个数是否可以组成三角形：任意两边之和大于第三边即可。
最简单的方法就是直接遍历数组，根据三角形的判断条件暴力枚举即可。
代码实现：
错误解法：暴力枚举
class Solution {
// 错误解法：暴力枚举
public int triangleNumber(int[] nums) {
int count = 0;
// 注意这里的i,j,k的位置，i最多只能倒带倒数第三个的位置,j....
for (int i = 0; i <= nums.length-3; i++) {
for (int j = i+1; j <= nums.length-2; j++) {
for (int k = j+1; k <= nums.length-1; k++) {
if (nums[i]+nums[j] > nums[k] &&
nums[i]+nums[k] > nums[j] &&
nums[k]+nums[j] > nums[i]
) {
count++;
}
}
}
}
return count;
}
}由于时间复杂度过高（O(N^3)），上面的代码肯定是跑不过的。
接下来，就是想想怎么优化？
我们知道三角形的判定还有一种简单方法：两小边之和大于最大边即可。那怎么找两小边呢？一个一个的去比较吗？这个肯定不现实。其实Arrays这类中有一个静态方法可以用来对数字进行排序( sort() ) ，知道了两小边之和，就是找最大边进行判断即可。
这里我们就通过一定的条件来优化了第三层循环，减少了循环的次数。
优化解法：定位两小边 和 最大边进行比较
class Solution {
// 优化解法一：定位两小边 和 最大边进行比较
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int count = 0;
for (int i = 0; i <= nums.length-3; i++) {
for (int j = i+1; j <= nums.length-2; j++) {
// k此时是三个数中最大值的下标
int k = j+1;
while (k < nums.length) {
if (nums[i]+nums[j] > nums[k]) {
count++;
k++;
} else {
// 由于数组是升序，因此后面的一定大于此时的值，因此无需判断了
break;
}
}
}
}
return count;
}
}既然可以定位 两小边，那么可不可以定位 最大边呢，然后找两小边进行比较呢？答案是可以的。
优化解法：固定最大边，比较另外两边
class Solution {
// 优化解法二：固定最大边，比较另外两边
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int count = 0;
for (int k = nums.length-1; k >=2; k--) {
// 开始寻找两小边的范围值
int i = 0;
int j = k-1;
while (i < j) {
if (nums[i]+nums[j] > nums[k]) {
count += (j-i); // 满足三角形的个数
j--; // i变化没意义
} else {
i++; // j变化没有意义
}
}
}
return count;
}
}注意：在固定最大边的优化方法中，我们只需要范围比较 nums[i] + nums[j] 与 nums[k] 的大小关系即可。没有去一个一个的遍历比较 比较 nums[i] + nums[j] 与 nums[k] 的大小关系。这就致使时间复杂度从 O(N^3) 降至 O(N^2)。
LCR 179.查找总价格为目标值的两个商品
题目：
购物车内的商品价格按照升序记录于数组
price。请在购物车中找到两个商品的价格总和刚好是target。若存在多种情况，返回任一结果即可。示例 1：
输入：price = [3, 9, 12, 15], target = 18 输出：[3,15] 或者 [15,3]示例 2：
输入：price = [8, 21, 27, 34, 52, 66], target = 61 输出：[27,34] 或者 [34,27]提示：
1 <= price.length <= 10^51 <= price[i] <= 10^61 <= target <= 2*10^6
思路： 很简单的思路，直接双层for循环遍历数组，去找和target的值即可。
代码实现：
错误解法：暴力枚举
class Solution {
// 错误解法：暴力枚举
public int[] twoSum(int[] price, int target) {
int[] ret = new int[2];
for (int i = 0; i < price.length; i++) {
// 如果从j=0开始的话，就会有重复的，且可能会出现i==j的情况
for (int j = i+1; j < price.length; j++) {
if (price[i]+price[j] == target) {
ret[0] = price[i];
ret[1] = price[j];
return ret;
}
}
}
return ret;
}
}上面的代码时间复杂度过高（O(N^2)），因此我们优化的方向就是降低时间复杂度为 O(N)。由于题目告诉我们了这个数组是有序的，并且知道了要查找的数据，因此我们可以对数据进行范围筛选。
通过上面的方法，我们会发现查找的效率直线上升了。其思路的时间复杂度为 O(N)。
正确解法：使用对撞指针，减少查询的次数，降低时间复杂度
class Solution {
public int[] twoSum(int[] price, int target) {
int[] ret = new int[2];
// 通过target的值来缩小范围遍历
int left = 0;
int right = price.length-1;
while (left < right) {
if (price[left]+price[right] > target) {
// 大于目标值，得减小
right--;
} else if (price[left]+price[right] < target) {
// 小于目标值。得增大
left++;
} else {
ret[0] = price[left];
ret[1] = price[right];
break;
}
}
return ret;
}
}通过上面两个题目，我们可以发现一个这样的规律：对撞指针能降低一个幂次级的时间复杂度。
例如：O(N^3) 使用对撞指针后，可以降低为 O(N^2)；O(N^2) 使用对撞指针后，可以降低为 O(N)。当然，最多也只能降低至 O(N)了，不可能直接降为O(1)。
15.三数之和
题目：
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
思路：根据题目给出的信息来看：我们要做的事情有两步：第一，找到符合三数之和为0的数；第二，对找到的数据进行去重操作。第一步的话，首先想到的就是暴力枚举找到符合要求的数据。但是找到数据之后的去重操作是比较难的，因为三个数的虽然总体是一样的，但是其内部的顺序却不同，我们无法直接判断，因此这里我们就需要对数据进行排序操作。但问题又来了：与其选择找出数据之后排序，不如直接在原数组上面进行排序操作。可能有小伙伴会疑惑：为什么要在原数组上进行排序呢？如下图所示：
排完序之后，我们会发现重复的数据长得一模一样，因此这里我们可以使用一个天然的去重容器set来处理，最终得到的结果就是我们想要的答案。
代码实现：
错误解法：暴力枚举
class Solution {
// 错误解法：暴力枚举
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// 1、先对数组整体排序
Arrays.sort(nums);
// 2、再去找符合条件的数据
for (int i = 0; i <= nums.length-3; i++) {
List<Integer> sub_list = new ArrayList<>();
for (int j = i+1; j <= nums.length-2; j++) {
for (int k = j+1; k <= nums.length-1; k++) {
// 这里可以优化一点点效率：>0的话，就直接跳出循环，
// 大于0，再继续往后走也没用(根本不可能出现==0的情况)
if (nums[i]+nums[j]+nums[k] == 0) {
sub_list.add(nums[i]);
sub_list.add(nums[j]);
sub_list.add(nums[k]);
List<Integer> integerList = new ArrayList<>(sub_list);
list.add(integerList);
// 每次插入数据之后，要及时清空，保证只有三个数据
sub_list.clear();
}
}
}
}
// 3、利用set对其去重
Set<List<Integer>> set = new HashSet<>();
// 遍历list将其中的元素插入set中
for (int i = 0; i < list.size(); i++) {
if (!set.contains(list.get(i))) {
set.add(list.get(i));
}
}
List<List<Integer>> new_list = new ArrayList<>();
// 遍历set中的元素插入到new_list
for (List<Integer> x : set) {
new_list.add(x);
}
return new_list;
}
}注意：上面代码的时间复杂度过大（三层for循环+两个遍历for循环）， 会超出时间限制。在最后一个将set中的元素插入new_list 中，可能有的小伙伴会写出下面的代码。
for (int i = 0; i < list.size(); i++) {
if (set.contains(list.get(i))) {
new_list.add(list.get(i));
}
}这个代码是有问题的，没有达到去重的目的。因为 list 可能中存在着多份相同的数据，但是在set 中只存在一份。因此当我们用 list 中的元素去遍历set 时，就会出现重复的元素，最终还是没有达到去重的效果。如下所示：
优化的思路有两个：1、对于查找数据时，使用对撞指针来进行优化。即通过最外层循环来固定一个数，然后再用对撞指针来找符合要求的数据。2、对去重的优化。set 去重虽然简单方便，但是两个for循环也带来了不少时间上的消耗。
1、优化查找数据：
正确解法：对撞指针优化查找数据
class Solution {
// 正确解法：使用对撞指针降低时间复杂度
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// 1、先对数组整体排序
Arrays.sort(nums);
// 2、再去找符合条件的数据
for (int i = 0; i <= nums.length-3; i++) {
List<Integer> sub_list = new ArrayList<>();
int j = i+1;
int k = nums.length-1;
while (j < k) {
if (nums[i]+nums[j]+nums[k] == 0) {
sub_list.add(nums[i]);
sub_list.add(nums[j]);
sub_list.add(nums[k]);
List<Integer> integerList = new ArrayList<>(sub_list);
list.add(integerList);
sub_list.clear();
// 只有一个增大，另一个减小，才可能达到相等
// 这里如果不是两个同时走的话，就会超出时间限制
j++;
k--;
} else if (nums[i]+nums[j]+nums[k] > 0) {
// 得减小，k--
k--;
} else { // < 0
// 得增加，j++
j++;
}
}
}
// 3、利用set对其去重
Set<List<Integer>> set = new HashSet<>();
// 遍历list将其中的元素插入set中
for (int i = 0; i < list.size(); i++) {
if (!set.contains(list.get(i))) {
set.add(list.get(i));
}
}
List<List<Integer>> new_list = new ArrayList<>();
// 遍历set中的元素插入到new_list中
for (List<Integer> x : set) {
new_list.add(x);
}
return new_list;
}
}上面的代码虽然可以通过全部的测试用例，但是时间效率非常之低。因此就要开始尝试看看能不能对去重操作进行优化。而最理想的优化就是能在找数据的同时去重。即在查找数据时，不把重复的数据算入其中，这就直接从源头上杜绝了去重的操作。那怎样才能找到不重复的数据呢？
我们会发现一个规律：当数据重复时，结果一定是相同的。即找到一组符合要求的数据之后，如果 j 对应的值 和 上一次 j 对应的值是一样的，那么就可以跳过，因为上一次 j 对应的值已经和其他值进行了结合检查。如果可以，那么就成了一次重复的数据；反之，上一次也检查过了。同理，k、i也是如此。当要注意一个数组越界问题。
class Solution {
// 正确解法：对撞指针+查找去重
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// 1、先对数组整体排序
Arrays.sort(nums);
// 2、再去找符合条件的数据
for (int i = 0; i <= nums.length-3; i++) {
// 与上一次的值相同，就不需要再进行重复的操作了
while (i-1 >= 0 && i <= nums.length-3 && nums[i] == nums[i-1]) {
i++;
}
// i对应的值一定是数组中最小的值，如果它都>0了，那肯定找不到了
while (i < nums.length && nums[i] > 0) {
i++;
}
List<Integer> sub_list = new ArrayList<>();
int j = i+1;
int k = nums.length-1;
while (j < k) {
if (nums[i]+nums[j]+nums[k] == 0) {
sub_list.add(nums[i]);
sub_list.add(nums[j]);
sub_list.add(nums[k]);
List<Integer> integerList = new ArrayList<>(sub_list);
list.add(integerList);
sub_list.clear();
// 只有一个增大，另一个减小，才可能达到相等
// 这里如果不是两个同时走的话，就会超出时间限制
j++;
k--;
// 如果和上一次的数据相同，则跳过
while (j < k && nums[j] == nums[j-1]) {
j++;
}
while (j < k && nums[k] == nums[k+1]) {
k--;
}
} else if (nums[i]+nums[j]+nums[k] > 0) {
// 得减小，k--
k--;
// 数据与上一次相同的话，查找出来的还是同样的结果
while (j < k && nums[k] == nums[k+1]) {
k--;
}
} else { // < 0
// 得增加，j++
j++;
// 数据与上一次相同的话，查找出来的还是同样的结果
while (j < k && nums[j] == nums[j-1]) {
j++;
}
}
}
}
return list;
}
}总的来说，这一题还是比较难的。既要想要去重的方法（利用set或者查找时排序相同的元素），还要避免时间复杂度过高的情况下查找数据（使用对撞指针进行优化处理）。
接下来，我们再来做一道与这个极其相似的题目。
18. 四数之和
题目：
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]提示：
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
思路：和三数之和简直就是孪生兄弟。 同样是先排序，再去查找数据（这里只展示优化后的思路和解法，想看推导过程和暴力枚举到优化的过程，可见三数之和）。
代码实现：
错误解法：用双层对撞指针代替四层for循环+内部去重
class Solution {
// 双层对撞指针会忽略一些数据
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
int i = 0;
int j = nums.length-1;
while (i < j) {
List<Integer> sub_list = new ArrayList<>();
// 注意left和right的取值
int left = i+1;
int right = j-1;
while (left < right) {
// 注意：对于内层循环来说，只有left和right是可变化的，i、j都是固定的
if (nums[i]+nums[j]+nums[left]+nums[right] == target) {
sub_list.add(nums[i]);
sub_list.add(nums[j]);
sub_list.add(nums[left]);
sub_list.add(nums[right]);
List<Integer> integerList = new ArrayList<>(sub_list);
list.add(integerList);
sub_list.clear();
left++;
right--;
while(left < right && nums[right] == nums[right+1]) {
right--;
}
while(left < right && nums[left] == nums[left-1]) {
left++;
}
} else if (nums[i]+nums[j]+nums[left]+nums[right] > target) {
right--;
while(left < right && nums[right] == nums[right+1]) {
right--;
}
} else {
left++;
while(left < right && nums[left] == nums[left-1]) {
left++;
}
}
}
i++;
j--;
while (i < j && nums[i] == nums[i-1]) {
i++;
}
while (i < j && nums[j] == nums[j+1]) {
j--;
}
}
return list;
}
}
上面代码的思路确实不错，的确可以减少不少时间的消耗，但是会漏掉一些数据。
当 nums = [-3, -1, 0, 2, 4, 5]、target = 0时，是找不到数据的。 感兴趣的小伙伴可以自己去测一测。（原本，我最先也是想到用这种方法来写，感觉效率应该会很高，但是后面经过调试发现，根本就找不出来上面的数据。）
正确解法：使用双层for循环+一层对撞指针+查找数据时去重
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
// 1、排序
Arrays.sort(nums);
// 2、开始找数据+去重操作
for (int i = 0; i <= nums.length-4;) {
for (int j = i+1; j <= nums.length-3;) {
List<Integer> sub_list = new ArrayList<>();
int left = j+1;
int right = nums.length-1;
while (left < right) {
if (((long)nums[i]+nums[j]+
nums[left]+nums[right]) == target) {
sub_list.add(nums[i]);
sub_list.add(nums[j]);
sub_list.add(nums[left]);
sub_list.add(nums[right]);
List<Integer> integerList = new ArrayList<>(sub_list);
list.add(integerList);
sub_list.clear();
left++;
right--;
while(left < right && nums[right] == nums[right+1]) {
right--;
}
while(left < right && nums[left] == nums[left-1]) {
left++;
}
} else if ((long)nums[i]+nums[j]+
nums[left]+nums[right] > target) {
right--;
while(left < right && nums[right] == nums[right+1]) {
right--;
}
} else {
left++;
while(left < right && nums[left] == nums[left-1]) {
left++;
}
}
}
j++;
while (j <= nums.length-3 && nums[j] == nums[j-1]) {
j++;
}
}
i++;
while (i >= 1 && i <= nums.length-4 && nums[i] == nums[i-1]) {
i++;
}
}
return list;
}
}注意：
1、
因此我们在计算四数之和时强转为了 long类型。
2、
总体来说：三数之和和四数之和还是有点难度的，不仅需要编码能力强，思路也要清新。
好啦！本期 双指针算法专题（2）的学习之旅就到此结束啦！我们下一期再一起学习吧！
