概述
leetcode上有个三数之和的题目：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
此题难度标注为中等，但通过率却只有24.9%。 看到题目，本来以为很快就能解决，没想到也花费了好几个小时，思考思考再思考，中途一度想放弃，在此记录一下解题过程。
方案一
最简单的方案，蛮力穷举即可解决，注意好边界检查即可。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
List<TripArray> ret1 = new ArrayList<>();
for(int i=0;i<nums.length-2;++i)
for(int j=i+1;j<nums.length-1;++j)
for(int z=j+1;z<nums.length;++z) {
if(nums[i] + nums[j] + nums[z] == 0) {
TripArray array = new TripArray(nums[i], nums[j],nums[z]);
if (ret1.contains(array) == false) { //避免重复
ret1.add(array);
ret.add(array.l);
}
}
}
return ret;
}
public static class TripArray {
private List<Integer> l = new ArrayList();
public TripArray(int x, int y, int z) {
int [] array = new int[]{x, y, z};
Arrays.sort(array);
l.add(array[0]);
l.add( array[1]);
l.add(array[2]);
}
public boolean equals(Object o) {
TripArray other = (TripArray)o;
return l.get(0) == other.l.get(0) && l.get(1) == other.l.get(1) && l.get(2) == other.l.get(2);
}
}
}
运行测试用例通过后直接提交，有个测试用例原始数组很长，没想到超时，以为是判断结果集中是否重复导致，于是想到可以先将原始数据排序后再寻找解。
方案二
先对原始数组排序，再穷尽，此时对重复的元素可以通过与其前一个元素比较，相同的元素值处理一遍，保证了结果集中不会有重复的元素
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ret = new ArrayList<>();
for(int i=0;i<nums.length-2;) {
for(int j=i+1;j<nums.length-1;) {
for(int z=j+1;z<nums.length;) {
if(nums[i] + nums[j] + nums[z] == 0) {
ret.add(Arrays.asList(nums[i],nums[j],nums[z]));
}
++z;
while(z<nums.length && nums[z] == nums[z-1]) ++z;
}
++j;
while(j<nums.length && nums[j] == nums[j-1]) ++j;
}
++i;
while(i<nums.length && nums[i] == nums[i-1]) ++i;
}
return ret;
}
}
一提交，还是超时，看了下题解，有说排序加双指针，有说对元素值是否大于0进行判断的，感觉排序加双指针思路本质跟当前方法是一样的，于是在当前思路上继续优化
方案三
利用数组有序性nums[i]<=nums[j]<=nums[z]，优化思路：
-
nums[i] > 0 , nums[i] + nums[j] + nums[z]肯定>0
-
nums[i]+nums[j]>0, nums[i] + nums[j] + nums[z]肯定>0
-
如果nums[i] + nums[j] + nums[z] == 0，此时nums[j]>0, 因nums[j]<nums[z],nums[i] + nums[j] + nums[z]依然>0
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> ret = new ArrayList<>(); for(int i=0;i<nums.length-2;) { if(nums[i]>0) break; for(int j=i+1;j<nums.length-1;) { if(nums[i]+nums[j]>0) break; for(int z=j+1;z<nums.length;) { if(nums[i] + nums[j] + nums[z] == 0) { ret.add(Arrays.asList(nums[i],nums[j],nums[z])); if(nums[j]>0) break; } ++z; while(z<nums.length && nums[z] == nums[z-1]) ++z; } ++j; while(j<nums.length && nums[j] == nums[j-1]) ++j; } ++i; while(i<nums.length && nums[i] == nums[i-1]) ++i; } return ret; } }
信心满满，没想到依然超时
方案四
发现只有找到一个解，nums[z]后续的元素不用再遍历了，可直接break, 此时扩展了方案三中优化思路三；同时对于nums[i]<0,nums[j]<0的情况，nums[z]可直接从第一个非负数搜索
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
if(nums.length<3) return ret;
Arrays.sort(nums);
int index = 0;
while (index<nums.length && nums[index]<0) ++index;
if(index == nums.length) return ret;
for(int i=0;i<nums.length-2;) {
if(nums[i]>0) break;
for(int j=i+1;j<nums.length-1;) {
int z = j+1;
if (nums[j] < 0 && z < index) z = index; //从第一个非负数开始
for(;z<nums.length;) {
int sum = nums[i] + nums[j] + nums[z];
if(sum > 0){
break;
}else if (sum == 0) {
ret.add(Arrays.asList(nums[i],nums[j],nums[z]));
break;
}
++z;
while(z<nums.length && nums[z] == nums[z-1]) ++z;
}
++j;
while(j<nums.length && nums[j] == nums[j-1]) ++j;
}
++i;
while(i<nums.length && nums[i] == nums[i-1]) ++i;
}
return ret;
}
}
依然超时，似乎根据元素与0的关系已经找不到出路了，有了放弃了念头
方案五
仔细分析，nums[i],nums[j]基本已无优化的空间，瓶颈似乎是在nums[z]上，此时是顺序查找第一个满足nums[i]+nums[j]+nums[z]=0的nums[z], 此时是一种线性试探，突然想到既然nums已经是有序了，可直接查找nums[z], 用二分法效率应该比现在的高，试试吧
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
if(nums.length<3) return ret;
Arrays.sort(nums);
int index = 0;
while (index<nums.length && nums[index]<0) ++index;
if(index == nums.length) return ret;
for(int i=0;i<nums.length-2;) {
if(nums[i]>0) break;
for(int j=i+1;j<nums.length-1;) {
if (nums[i] + nums[j] >0) break;
int z = j+1;
if (nums[j] < 0 && z < index) z = index;
int key = -(nums[i] + nums[j]);
int x = Arrays.binarySearch(nums, z, nums.length, key);
if(x>0) {
ret.add(Arrays.asList(nums[i],nums[j],nums[x]));
}
++j;
while(j<nums.length && nums[j] == nums[j-1]) ++j;
}
++i;
while(i<nums.length && nums[i] == nums[i-1]) ++i;
}
return ret;
}
}
提交，没想到竟然没有超时，真是柳岸花明，刷题真是不放弃，不断优化的过程。
最后
以上就是谦让麦片为你收集整理的三数之和为0的解题过程的全部内容，希望文章能够帮你解决三数之和为0的解题过程所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复