frontpage新建网站,备案关闭网站,wordpress 百度地图插件,百度竞价渠道户题目链接#xff1a;18. 四数之和 - 力扣#xff08;LeetCode#xff09;
这道题是在三数之和上改编出来的#xff0c;在写这道题之前可以尝试以下三数之和#xff08;15. 三数之和 - 力扣#xff08;LeetCode#xff09;#xff09;#xff1b;
1.常规解法#xf…题目链接18. 四数之和 - 力扣LeetCode
这道题是在三数之和上改编出来的在写这道题之前可以尝试以下三数之和15. 三数之和 - 力扣LeetCode
1.常规解法会超时
由于这道题的结果不能出现含相同元素的三元组则可以先对目标数组排以防出现结果中元素相同但顺序不同的情况
接下可以遍历这个数组先找到所有的三元组再挑选出符合条件的三元组代码如下 public ListListInteger fourSum(int[] nums, int target) {ListListInteger ret new ArrayList();int n nums.length;Arrays.sort(nums);for (int i 0; i n; i) {for (int j i 1; j n; j) {for (int k j 1; k n; k) {for (int l k 1; l n; l) {if ((long)nums[i] (long)nums[j] (long)nums[k] (long)nums[l] (long)target) {ListInteger list new ArrayList();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);list.add(nums[l]);if (!ret.contains(list)) {ret.add(list);}}}}}}return ret;}
注意我们再进行判断时涉及到四个数据相加由于整形数据的最大值是2147483647,会出现1000000000 1000000000 1000000000 1000000000 -294967296的情况这与实际情况不符这时就需要类型转换由于long类型的数据范围更大就可以将int转化为long再相加比较。
2.双指针算法
和三数之和一样我么可以先固定最后一个数在前面的数中找到和为target - 最后一个数
因为有去重操作可以先对数组从小到大排序
先定义四个指针p1p2leftrightp1指向最后一个数p2指向倒数第二个数left指向第一个数right指向p2前一个数
现保持p1和p2不动让left与right相向运动若(long)nums[left] (long)nums[right] (long)nums[p1] (long)nums[p2] target则将这个四元组添加到结果中由于不能出现出重复的四元组就需要去除与left和right指向元素相同的元素若(long)nums[left] (long)nums[right] (long)nums[p1] (long)nums[p2] target由单调性知以left为基准right左边的数均小于right指向的元素相加之后结果必小于target就需要将left向右移动一位若(long)nums[left] (long)nums[right] (long)nums[p1] (long)nums[p2] target由单调性知以right为基准left右边的元素均大于left指向的元素相加之后结果必大于target就需要将right左移一位
当left与right相遇后内层的一轮循环就结束了就需要将p2向左移动一位同样的也需要进行去重操作除去与p2指向元素相同的元素
当p21时p2已经走完一遍就需要向左移动p1继续下一轮循环同样的也需要进行去重操作去除与p1指向元素相同的元素流程图与代码如下 public ListListInteger fourSum(int[] nums, int target) {ListListInteger ret new ArrayList();Arrays.sort(nums);int n nums.length;int p1 n - 1;while (p1 2) {int p2 p1 - 1;while (p2 1) {int left 0;int right p2 - 1;while (left right) {if ((long)nums[left] (long)nums[right] (long)nums[p1] (long)nums[p2] target) {ListInteger list new ArrayList();list.add(nums[left]);list.add(nums[right]);list.add(nums[p1]);list.add(nums[p2]);ret.add(list);int numLeft nums[left];while (nums[left] numLeft left right) {left;}int numRight nums[right];while (nums[right] numRight left right) {right--;}} else if ((long)nums[left] (long)nums[right] (long)nums[p1] (long)nums[p2] target) {left;} else {right--;}}int numP2 nums[p2--];while (nums[p2] numP2 p2 1) {p2--;}}int numP1 nums[p1--];while (nums[p1] numP1 p1 2) {p1--;}}return ret;}
希望读者指出不足之处
