河南智能网站建设平台,百度关键词优化企业,WordPress采集懒加载的图片,广州外贸型网站给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意#xff1a;答案中不可以包含重复的三元组。 输入判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 输入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] 。
注意输出的顺序和三元组的顺序并不重要。 梦开始的地方两数之和这其实和两数之和的做法大同小异三数之和我们开始将其拆分成一数枚举剩余两数凑结果即可 因为我们利用类似于滑动窗口类似的技巧所以我们必须要求该数组是一个有序的数组所以我们先要对数组进行排序 Arrays.sort(nums);
然后对数组中的每个元素进行枚举相当于确定一个数 //因为我们这是三数之和所以我们的第一个数醉倒可以枚举到倒数第三个数for (int i 0; i nums.length - 2; i) {}
因为在遍历的时候我们可以优先的对过程进行剪枝操作
1.如果前面3个数相加已经大于零后面的数就不可能在等于零故可以剪去
2.如果第一个数加上最大的两个数都小于零最大的数都小于零更何况中间的数呢故可以进行剪去
3.因为题目中不允许我们又重复的结果出现我们也可以将其进行剪去
那么我们就可以得到如下 int x nums[i];//如果前三个数之和大于零后面的数之和就不可能有等于零的情况if (nums[i] nums[i 1] nums[i 2] 0) {break;}//加上两个最大的值也小于零直接跳过这个x值if (nums[i] nums[n - 1] nums[n - 2] 0) {continue;}//为了避免重复的情况的发生如果相等则直接跳过if (i0nums[i] nums[i - 1]) {continue;} 现在的问题就转换成在固定的区间内找到满足target的两数之和通过双指针不断的从两边收缩进行求解 int j i 1;int k n-1;while (j k) {//两数和int sum x nums[k] nums[j];//如果大于说明k指向的数太大了往左移if (sum 0) {k--;//如果小于说明j指向的数太小了往右移} else if (sum 0) {j;//如果相等先将3个符合条件的数添加到list中去} else {list.add(Arrays.asList(x,nums[j],nums[k]));//为了避免结果重复左指针碰到相邻重复的直接跳过while (j k nums[j] nums[j1]) {j;}j;// //为了避免结果重复右指针碰到相邻重复的直接跳过while (j k nums[k] nums[k-1]) {k--;}k--;}}
源码如下
public ListListInteger threeSum(int[] nums) {ListListInteger list new ArrayList();//先对入参进行判断如果nums为空直接返回if (nums null || nums.length 0) {return list;}Arrays.sort(nums);int n nums.length;//枚举每一个元素设置两个指针进行跑for (int i 0; i nums.length - 2; i) {int x nums[i];//如果前三个数之和大于零后面的数之和就不可能有等于零的情况if (nums[i] nums[i 1] nums[i 2] 0) {break;}//加上两个最大的值也小于零直接跳过这个x值if (nums[i] nums[n - 1] nums[n - 2] 0) {continue;}//为了避免重复的情况的发生如果相等则直接跳过if (i0nums[i] nums[i - 1]) {continue;}int j i 1;int k n-1;while (j k) {int sum x nums[k] nums[j];if (sum 0) {k--;} else if (sum 0) {j;} else {list.add(Arrays.asList(x,nums[j],nums[k]));while (j k nums[j] nums[j1]) {j;}j;while (j k nums[k] nums[k-1]) {k--;}k--;}}}return list;}
