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: 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]
]
这个问题可以看作TwoSum的升级版，其实解题思路就是遍历一遍S，时间复杂度为O（n），然后就转变为TwoSum问题，TwoSum问题的时间复杂度为O（n），于是3Sum的时间复杂度为O（n2）。
下面这个解法的思路是通过两个指针（low和high）的移动来遍历，注意遍历一遍S时遇到的相同数字通过i＋＋来跳过避免重复，low和high指针也对相同的数字进行跳过避免重复，这样就避免了使用Set来去掉重复元素。
public class Solution {
public static List<List> threeSum(int[] nums) {
Arrays.sort(nums);
List<List> result=new ArrayList();
for(int i=0;i<nums.length-2;i++) { if(i>0)
while((nums[i]==nums[i-1])&&(i<nums.length-2)) i++;
int low=i+1,high=nums.length-1,num=-nums[i];
while(low<high)
{
if(nums[low]+nums[high]==num)
{
result.add(Arrays.asList(nums[i],nums[low],nums[high]));
while((low<high)&&(nums[low]==nums[low+1])) low++;
while((low<high)&&(nums[high]==nums[high-1])) high--; low++; high--; } else if(nums[low]+nums[high]>num)
high--;
else
low++;
}
}
return result;
}
}
Ps：这里需要注意
while((low<high)&&(nums[low]==nums[low+1]))
与
while((nums[low]==nums[low+1])&&(low<high))
的区别，同样是判断条件在判断时是有先后区分的，前者在判断nums[low]==nums[low+1]时已完成了low<high的判断，即此时的low均小于high。后者会先判断nums[low]==nums[low+1]，若此时low＝＝high＝＝nums.length－1，则nums［low＋1］则会越界，即使有low<high这个条件限制也无用。把low<high放在while判断条件的前面可以有效防止越界。
所以应注意判断条件的先后顺序。
下面的算法是自己根据LeetCode上2Sum高票答案写的，利用了Map解决2Sum问题，这样虽然也可以Accept，但是遍历了 所有的元素且还要通过Set去掉重复元素，所以时间效率和空间效率不如上面的算法好。但是作为复习2Sum还是极好的。2Sum算法的重点是一边遍历一边向Map中添加元素，这个算法一开始我误以为是把所有元素都添加进Map后再通过contendsKey（）函数寻找是否存在，这是不对的。
public class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result=new ArrayList();
for(int i=0;i<nums.length-2;i++) { if(i>0)
while((nums[i]==nums[i-1])&&(i<nums.length-2)) i++;
Map<Integer,Integer> zan = new HashMap<Integer,Integer>();
for(int j=i+1;j<nums.length;j++)
{
if(zan.containsKey(-(nums[i]+nums[j])))
result.add(Arrays.asList(nums[i],zan.get(-(nums[i]+nums[j])),nums[j]));
zan.put(nums[j], nums[j]);
}
}
Set<List<Integer>> merge=new HashSet();
for(List<Integer> a:result)
merge.add(a);
List<List<Integer>> newresult=new ArrayList();
for(List<Integer> b:merge)
newresult.add(b);
return newresult;
}
}
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1,2,1,-4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
3Sum Closest 问题是3Sum问题的变形，考虑把a＋b＋c＝0的3Sum问题变为a+b+c=target的问题即可。时间复杂度与3Sum问题相同，均为O（n2）。
public class Solution {
public static int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int tmp=Integer.MAX_VALUE;
int result = 0;
for(int i=0;i<nums.length-2;i++) { if(i>0) while((nums[i]==nums[i-1])&&(i<nums.length-2)) i++;
int low=i+1,high=nums.length-1,t=target-nums[i];
while(low<high)
{
if(Math.abs(nums[low]+nums[high]+nums[i]-target)<tmp)
{
tmp=Math.abs(nums[low]+nums[high]+nums[i]-target);
result=nums[low]+nums[high]+nums[i];
}
if(nums[low]+nums[high]==t) return target;
else if((low<high)&&(nums[low]+nums[high]>t)) high--;
else if((low<high)&&(nums[low]+nums[high]<t)) low++;
}
}
return result;
}
