面试经典150题——三数之和

题目来源

力扣每日一题；题序：15

我的题解

方法一 暴力解法 超时

进行三重循环遍历，判断和是否为0，若为0，则将对应的值组合成List并加入Set。

时间复杂度：O($n^3$)
空间复杂度：O(n)

public List<List<Integer>> threeSum(int[] nums) {Set<List<Integer>> resSet=new HashSet<>();int n=nums.length;for(int i=0;i<n-2;i++){for(int j=i+1;j<n-1;j++){for(int k=j+1;k<n;k++){if(nums[i]+nums[j]+nums[k]==0){List<Integer> t=Arrays.asList(nums[i],nums[j],nums[k]);t.sort((a,b)->a-b);resSet.add(t);}}}}return new ArrayList<>(resSet);
}

方法二 扩展两数之和（双指针）

先确定一个数，然后使用两数之和的解法进行计算。注意需要去重，即在求两数之和的过程中需要将去掉重复的元素。

时间复杂度：O($n^2$)。
空间复杂度：O(n)

public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> res=new ArrayList<>();for(int i=0;i<nums.length;){List<List<Integer>> t=twoSum(nums,-nums[i],i);int pre=nums[i];while(i<nums.length&&nums[i]==pre)i++;res.addAll(t);}return res;
}
public List<List<Integer>> twoSum(int[] nums,int  target,int index){int left=index+1,right=nums.length-1;List<List<Integer>> res=new ArrayList<>();while(left<right){int tNum=nums[left]+nums[right];int preLeft=nums[left];int preRight=nums[right];if(index==left){left++;continue;}if(index==right){right--;continue;}if(tNum==target){List<Integer> t=Arrays.asList(-target,nums[left],nums[right]);res.add(t);while(left<right&&nums[left]==preLeft)left++;while(right>left&&nums[right]==preRight)right--;}else if(tNum<target){while(left<right&&nums[left]==preLeft)left++;}else{while(right>left&&nums[right]==preRight)right--;}}return res;
}

方法三 扩展为通用的n数之和

时间复杂度：O($n^2$)。
空间复杂度：O(n)

public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> resList = nSum(nums, 0, 3, 0);return resList;
}public  List<List<Integer>> nSum(int[] nums, int target, int n, int start) {int len = nums.length;List<List<Integer>> res = new ArrayList<>();if (n == 2) {int left = start, right = len - 1;while (left < right) {int temp = nums[left] + nums[right];int l = nums[left], r = nums[right];if (temp < target) {while (left < right && l == nums[left])left++;} else if (temp > target) {while (left < right && r == nums[right])right--;} else {List<Integer> sub = new ArrayList(Arrays.asList(nums[left], nums[right]));res.add(sub);while (left < right && l == nums[left])left++;while (left < right && r == nums[right])right--;}}} else {for (int i = start; i < len; i++) {List<List<Integer>> subList = nSum(nums, target - nums[i], n - 1, i + 1);for (List<Integer> list : subList) {list.add(nums[i]);res.add(list);}while (i < len - 1 && nums[i] == nums[i + 1])i++;}}return res;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~