三数之和

由于这道题的结果不能出现含相同元素的三元组则可以先对目标数组排以防出现结果中元素相同但顺序不同的情况

接下可以遍历这个数组先找到所有的三元组再挑选出符合条件的三元组代码如下

public

nums.length;Arrays.sort(nums);for

(int

ArrayList();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);list.add(nums[l]);if

ret;}

注意我们再进行判断时涉及到四个数据相加由于整形数据的最大值是2147483647,会出现1000000000

1000000000

-294967296的情况这与实际情况不符这时就需要类型转换由于long类型的数据范围更大就可以将int转化为long再相加比较。

2.双指针算法

和三数之和一样我么可以先固定最后一个数在前面的数中找到和为target

最后一个数

先定义四个指针p1p2leftrightp1指向最后一个数p2指向倒数第二个数left指向第一个数right指向p2前一个数

现保持p1和p2不动让left与right相向运动若(long)nums[left]

(long)nums[right]

target则将这个四元组添加到结果中由于不能出现出重复的四元组就需要去除与left和right指向元素相同的元素若(long)nums[left]

(long)nums[right]

target由单调性知以left为基准right左边的数均小于right指向的元素相加之后结果必小于target就需要将left向右移动一位若(long)nums[left]

(long)nums[right]

target由单调性知以right为基准left右边的元素均大于left指向的元素相加之后结果必大于target就需要将right左移一位

当left与right相遇后内层的一轮循环就结束了就需要将p2向左移动一位同样的也需要进行去重操作除去与p2指向元素相同的元素

当p21时p2已经走完一遍就需要向左移动p1继续下一轮循环同样的也需要进行去重操作去除与p1指向元素相同的元素流程图与代码如下

public

ArrayList();Arrays.sort(nums);int

nums.length;int

ArrayList();list.add(nums[left]);list.add(nums[right]);list.add(nums[p1]);list.add(nums[p2]);ret.add(list);int

numLeft