2sum, 3sum, 4sum和3sum closest总结

2sum, 3sum, 4sum和3sum closest是四道类似的题目，后面三个都是2sum的延伸。

1，2sum
给定一个数组numbers[]和一个目标数值target，从数组中找到两个元素，使它们的和等于目标元素。返回这两个值的索引indices，并且index1 大于index2。（假设只有一个结果）
例如：输入: numbers={2, 7, 11, 15}, target=9
           输出: index1=1, index2=2 （不是zero-based）

我们用hash来实现这道题，key中存放数组里面元素的值number[i], value中存放对应的下标，hash(numbers[i], i)。我们从第一个元素开始遍历，检查表中是否存在一个key与target- numbers[i]相等，如果存在，那么结果就是这个key对应的value和当前的i的值，它们就是我们要找的下标；如果不存在就把<number[i], i>放入哈希表中，我们看到他的输出不是zero-based的,要将它们原始下标加1. 代码如下：

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int tem = target - nums[i];
            if(hm.containsKey(tem)){
                result[0] = hm.get(tem) + 1;
                result[1] = i + 1;
            } else {
                hm.put(nums[i], i);
            }
        }
        return result;
    }
}

2，3sum
给定一个数组nums[]，从中找出三个数使它们的和等于0，输出所有可能的结果。
例如：给定数组 nums[] = {-1 0 1 2 -1 -4};
           输出： (-1, 0, 1), (-1, -1, 2)  **结果集中的元素是有序的，并且结果集中不能重复

3sum是2sum的变形，我们用两个指针来处理这个问题，分别为left和right。因为结果是有序的，我们首先对数组进行排序。例如我们查找到第i个元素开查找，循环的开始right都指向最后一个元素，left指向i的下一个元素i + 1；然后比较nums[i] + nums[left] + nums[right] 是否为零，如果为零就输出结果，然后让left ++，right --，继续查找其他可能的结果；如果它们的和小于零，我们就让left ++； 如果它们的和大于零，就让right--；这个过程中我们要保证left始终小于right。代码如下：

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        Arrays.sort(nums);
        if(nums == null || nums.length < 3) return llist;
        for(int i = 0; i < nums.length; i++) {
            //optimize, skip duplicate element
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1; 
            int r = nums.length - 1;
            while( l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if(sum > 0) {
                    r --;
                } else if(sum < 0) {
                    l ++;
                } else {
                    list.add(nums[i]);
                    list.add(nums[l]);
                    list.add(nums[r]);
                    llist.add(new ArrayList<Integer>(list));
                    list.clear();
                    while(l < r && nums[l] == nums[l + 1]) l ++;
                    while(l < r && nums[r] == nums[r - 1]) r --;
                    l ++;
                    r --;
                }
             }
        }
        return llist;
    }
}

3，4sum
给定一个数组nums[]和一个目标元素target，找出四个数，使他们的和等于target，输出所有可能的结果。
例如：给定数组nuts[] = {1 0 -1 0 -2 2} , target = 0.
输出:(-1,  0, 0, 1)， (-2, -1, 1, 2)， (-2,  0, 0, 2)
**结果集中的元素是有序的，并且结果集中不能重复

在3sum上的变形，首先也要对数组进行排序，然后我们只需要多加一个循环，用两个指针进行比较，不过只是用四个数的和与target比较而已。代码如下：

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        
        if(nums == null || nums.length < 4) return llist;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 3; i++) {
            for(int j = i + 1; j < nums.length - 2; j++) {
                int l = j + 1;
                int r = nums.length - 1;
                while(l < r) {
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if(sum > target) {
                        r --;
                    } else if (sum < target) {
                        l ++;
                    } else {
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[l]);
                        list.add(nums[r]);
                        if(!llist.contains(list))
                            llist.add(new ArrayList<Integer>(list));
                        list.clear();
                        while(l < r && nums[l] == nums[l+1]) l ++;
                        while(l < r && nums[r] == nums[r-1]) r --;
                        l ++;
                        r --;
                    }
                }
            }
        }
        
        return llist;
    }
}

4，3sum Closest
给定一个数组nums[] 和一个目标元素target，从数组中找出三个元素，使它们的和最接近target，输出这三个元素的和。
例如：nums[] = {-1 2 1 -4}, and target = 1
输出：2     **因为 (-1 + 2 + 1 = 2)距离target最近

我们先按照3sum的思路，首先对数组进行，然后设定两个指针left和right，从第一个元素开始处理。理想情况下，如果找到三个数的和等于target，它们的距离为0，直接输出target。但是我们不能保证数组中一定存在三个数的和等于target，我们首先维护一个变量des，让它记录三个数的和与target的差值，每次比较des与当然的循环中的currentdes，如果currentdes小于全局的des，我们就用result记录当前三个数的和，直接从代码开来比较直观：

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums == null || nums.length < 3) return -1;
        int des = Integer.MAX_VALUE;
        int result = 0;
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length; i++) {
            int l = i + 1;
            int r = nums.length - 1;
            while(l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == target) {
                    return target;
                } else if(sum < target) {
                    if(target - sum < des) {
                        des = target - sum;
                        result = sum;
                    } 
                    l ++;
                } else {
                    if(sum - target < des) {
                        des = sum - target;
                        result = sum;
                    } 
                    r --;
                }
            }
        }
        return result;
        
    }
}