Given an array
nums
of n integers, are there elements a, b, c innums
such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note:
The solution set must not contain duplicate triplets.
给一个数组,找到里面满足三数和为0的所有三元数组。数组不可重复。
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
这道题拿到第一个思路就是三轮遍历,然后找到其中和为0的三个数
但是,这样的时间复杂度为o(n3),效率低的令人发指,更不用提这样做还没有去考虑如何去重。
最终博主通过的方法是运用数学思维进行分析。
1、首先三个数相加为零,所以三个数必然有正有负。全为负数,或者全为正数,相加是不然不满足条件。
2、既然需要将正负数分开,索性就用先对数组进行排序,这样更容易处理重复问题。
3、因为没有说明数组的特征,所以这里默认为基本无序数组,所以优先选择快速排序,这里的时间复杂度为o(nlgn)~o(n2)。
4、假设三个数分别为left,point,right。先固定一个数left,剩下俩数point和right从首尾开始向中间逼近。逼近的规则为:(这里时间复杂度为o(1)~o(n)取决于lefe位置)
4.1如果三数和小于0,那么便意味着三个数偏小,left为固定的,right为最右边的数已经是最大的了,只有将point向左移动一位使得三数之和变大。
4.2如果三数和大于0,与上面相反,则让right向左移动一位使right变小,使得总和变小。
4.3如果三数和等于0,那么这三个数即为目标数组。
4.4在上述过程的point以及right移动过程中可以通过前后对比的方式实现去重。
5、当4过程将数组遍历完毕,便将最左的left向右移动一位,继续重复4过程,直到left移动到倒数第三的位置,无法继续移动为止。这里时间复杂度为o(n2)
6、由于1,所以left移动到0以后不可能存在三个数满足条件,所以实际上5过程不需要移动到最右边,到0即可。这里时间复杂度为o(1)~o(n2)取决于负数的个数。
所以上述的思路,时间复杂度为o(nlogn)~o(n2),效率远远高于三轮遍历的o(n3)。
代码如下:
public List<List<Integer>> threeSum1(int[] nums){ int i, j, k; List<List<Integer>> out = new ArrayList<>(); Arrays.sort(nums); for(i=0;i<nums.length-2&&nums[i]<=0;i++){ if (i > 0 && nums[i] == nums[i - 1]) { continue; } j = i + 1; k = nums.length - 1; while (j < k) { if (nums[i] + nums[j] + nums[k] == 0) { out.add(Arrays.asList(nums[i], nums[j], nums[k])); 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) { j++; } else { k--; } } } return out; }