LeetCode OJ 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

---

【问题分析】

kSUM系列的问题有好多个，如下：

我们对这几个题目分别分析并进行总结。

【思路】

1. Two Sum

解决这个问题可以直接利用两层循环对数组进行遍历，这样的时间复杂度为O(N²)。一个巧妙的办法是利用java中的HashMap来解决这个问题，代码如下：

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

由于HashMap的查询效率很高，HashMap的一些操作技巧：http://jiangzhenghua.iteye.com/blog/1196391

2. Two Sum II - Input array is sorted

这个two sum问题中，数组中的元素是已经排序的，我们从数组的头和尾向数组中间靠拢，如果头尾元素相加大于target，则尾指针向前移动一步，如果小于target，则头指针向后移动一步，直到两指针相遇或者相加结果为target。示例如下：[2,3,4,5] target = 7

思路很简单，代码如下：

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        if(numbers == null || numbers.length < 2) return result;
        
        int left = 0, right = numbers.length-1;
        while(left < right){
            int cur = numbers[left] + numbers[right];
            if(cur == target){
                result[0] = left+1;
                result[1] = right+1;
                return result;
            }
            else if(cur < target){
                left++;
            }
            else{
                right--;
            }
        }
        return result;
    }
}

可见，排序后的two sum效率还是很高的。

 3. Three sum

The idea is to sort an input array and then run through all indices of a possible first element of a triplet. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array. Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that.

结合two sum和Two Sum II - Input array is sorted我们可以比较好解决这个问题。上面这段话的思路是：先对数组进行排序，然后遍历排序后数组，把每一个元素当做三元组的开始元素，剩下的两个元素的查找和Two Sum II是相同的。在这个过程中需要注意的就是去重，一些重复出现的元素要跳过。代码如下：

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); 
        List<List<Integer>> result = new LinkedList<>();
        for(int i = 0; i < nums.length-2; i++){
            if(i == 0 || (i>0 && nums[i] != nums[i-1])){
                int target = 0 - nums[i];
                int left = i + 1;
                int right = nums.length - 1;
                while(left < right){
                    if(nums[left] + nums[right] == target){
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        while(left < right && nums[left] == nums[left+1]) left++;
                        while(left < right && nums[right] == nums[right-1]) right--;
                        left++; right--;
                    }
                    else if (nums[left] + nums[right] < target) 
                         left ++;
                    else right--;
                }
            }
        }
        return result;
    }
}

4. 3Sum Closest

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的基础上做了一点变化，要在所有2元组中找到与目标值最接近的三元组的和。我的思路和上一个题目类似，先对数组进行排序，然后在遍历过程中如果发现了更接近的元组的和，则更新最接近的值。如果发现了和值有和目标值相等的，则直接返回目标值。代码如下：

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = nums[0]+nums[1]+nums[2];
        for(int i = 0; i < nums.length-2; i++){
            int left = i+1, right = nums.length-1;
            while(left < right){
                int cur = nums[i] + nums[left] + nums[right];
                if(cur == target) return cur;
                else if(cur > target) right--;
                else left++;
                if(Math.abs(cur-target) < Math.abs(closest-target))
                    closest = cur;
            }
        }
        return closest;
    }
}

5. 4sum

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

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

这个问题的解决可以借鉴3 sum的思路，只要在3sum外层再增加一层循环即可，代码如下：

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        for(int i = 0; i < nums.length-3; i++){
            if(i == 0 || (i>0 && nums[i] != nums[i-1])){
                int curtarget1 = target - nums[i];
                for(int j = i+1; j < nums.length-2; j++){
                    if(j == i+1 || (j>i+1 && nums[j] != nums[j-1])){
                        int curtarget2 = curtarget1 - nums[j];
                        int left = j + 1;
                        int right = nums.length - 1;
                        while(left < right){
                            if(nums[left] + nums[right] == curtarget2){
                                result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                                while(left < right && nums[left] == nums[left+1]) left++;
                                while(left < right && nums[right] == nums[right-1]) right--;
                                left++; right--;
                            }
                            else if (nums[left] + nums[right] < curtarget2) 
                                left ++;
                            else right--;
                        }
                    }
                }
            }
        }
    return result;
    }
}

自此，这几个解锁的N sum的题目就做完了，这种题目用回溯法适合不适合呢？

另外需要注意在求解的时候要去掉重复的解，如果排序后的元素是a,b,c,d，求解过程如果选定的元素和上一个选定的元素是相同的，则可以直接跳过该元素。至于为什么是这样，大家可以思考一下。