[LeetCode] 015--3Sum --Medium--

本文主要是介绍[LeetCode] 015--3Sum --Medium--，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

提示 Array Two Pointers
类似题目 (M) Two Sum (M) 3Sum Closest (M) 4Sum (M) 3Sum Smaller

原题链接：https://leetcode.com/problems/3sum/

大概意思是：给出一个整型数组，求出所有和为0的三个数。要求，1数字顺序小到大；2不允许重复
思路：跟上一道题TwoSum的思路一样，排序然后两边向中间夹逼。

解题语言：java
方法一双向指针，时间复杂度O(nlogn+n+n+a*b+a*b)=O(a*b），其中a、b分别为正数、负数的个数

public class Solution {public List<List<Integer>> threeSum(int[] nums) {List<Integer> pos = new ArrayList<Integer>();List<Integer> neg = new ArrayList<Integer>();List<Integer> zoer = new ArrayList<Integer>();// Arrays.sort(nums)List<List<Integer>> threeSumAll = new ArrayList<List<Integer>>();if (nums == null || nums.length <= 2) {return threeSumAll;}for (int i = 0; i < nums.length; i++) {if (nums[i] < 0) {neg.add(nums[i]);} else if (nums[i] == 0) {zoer.add(0);} else {pos.add(nums[i]);}}Collections.sort(neg);Collections.sort(zoer);Collections.sort(pos);// System.out.println("neg.toString():::" + neg.toString());// System.out.println("zoer.toString():::" + zoer.toString());// System.out.println("pos.toString():::" + pos.toString());// 包含0的情况if (zoer.size() > 0) {List<Integer> oneList = new ArrayList<Integer>(neg);oneList.addAll(pos);System.out.println("oneList.toString():::" + oneList.toString());int left, right;left = 0;right = oneList.size() - 1;while (left < right) {if (oneList.get(left) + oneList.get(right) == 0) {if (left + 1 < right - 1&& oneList.get(left) == oneList.get(left + 1)&& oneList.get(right) == oneList.get(right - 1)) {left = left + 1;right = right - 1;continue;}// else{List<Integer> threeSum = new ArrayList<Integer>();threeSum.add(oneList.get(left));threeSum.add(0);threeSum.add(oneList.get(right));threeSumAll.add(threeSum);left = left + 1;right = right - 1;// }} else if (oneList.get(left) + oneList.get(right) < 0) {left = left + 1;} else {right = right - 1;}}// 特殊情况包含3个0if (zoer.size() > 2) {List<Integer> threeSum = new ArrayList<Integer>();threeSum.add(0);threeSum.add(0);threeSum.add(0);threeSumAll.add(threeSum);}}//      计算一个正数，两个负数的情况for (int i = 0; i < pos.size(); i++) {if (i + 1 < pos.size() && pos.get(i) == pos.get(i + 1)) {continue;}int positive = pos.get(i);int left, right;left = 0;right = neg.size() - 1;int Negative = Integer.MAX_VALUE;while (left < right) {if (neg.get(left) + neg.get(right) + positive == 0&& Negative != neg.get(left)) {// System.out.println("neg.get(left):::"// + neg.get(left));// System.out.println("neg.get(right):::"// + neg.get(right));// System.out.println("Negative:::" + Negative);List<Integer> threeSum = new ArrayList<Integer>();threeSum.add(neg.get(left));threeSum.add(neg.get(right));threeSum.add(positive);threeSumAll.add(threeSum);Negative = neg.get(left);left = left + 1;right = right - 1;} else if (neg.get(left) + neg.get(right)+ positive < 0) {left = left + 1;} else {right = right - 1;}}}//      计算一个负数，两个正数的情况for (int i = 0; i < neg.size(); i++) {if (i + 1 < neg.size() && neg.get(i) == neg.get(i + 1)) {continue;}int negative = neg.get(i);int left, right;left = 0;right = pos.size() - 1;int Positive = Integer.MAX_VALUE;while (left < right) {if (pos.get(left) + pos.get(right) + negative == 0&& Positive != pos.get(left)) {List<Integer> threeSum = new ArrayList<Integer>();threeSum.add(negative);threeSum.add(pos.get(left));threeSum.add(pos.get(right));threeSumAll.add(threeSum);Positive = pos.get(left);left = left + 1;right = right - 1;} else if (pos.get(left) + pos.get(right) + negative < 0) {left = left + 1;} else {right = right - 1;}}}return threeSumAll;}}

方法二：
csdn的一个大神解答，思路，使用排序之后夹逼的方法，总的时间复杂度为O(n^2+nlogn)=(n^2),空间复杂度是O(n),代码简介清晰，赞！！！
这里上原链接：http://blog.csdn.net/linhuanmars/article/details/19711651

public class Solution {public List<List<Integer>> threeSum(int[] nums) {ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();if (nums == null || nums.length <= 2)return res;Arrays.sort(nums);for (int i = nums.length - 1; i >= 2; i--) {if (i < nums.length - 1 && nums[i] == nums[i + 1])continue;ArrayList<List<Integer>> curRes = twoSum(nums, i - 1, -nums[i]);for (int j = 0; j < curRes.size(); j++) {curRes.get(j).add(nums[i]);}res.addAll(curRes);}return res;}private ArrayList<List<Integer>> twoSum(int[] num, int end, int target) {ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();if (num == null || num.length <= 1)return res;int l = 0;int r = end;while (l < r) {if (num[l] + num[r] == target) {ArrayList<Integer> item = new ArrayList<Integer>();item.add(num[l]);item.add(num[r]);res.add(item);l++;r--;while (l < r && num[l] == num[l - 1])l++;while (l < r && num[r] == num[r + 1])r--;} else if (num[l] + num[r] > target) {r--;} else {l++;}}return res;}
}