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: 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;
    }