2Sum

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2.

最开始的思路是比较暴力的解法，设两个嵌套循环，让数组内元素两两相加，直到某两者之和等于目标值，即为所求解，复杂度O(n^2)。

优化：
利用HashMap，只需遍历一次，O(n)。
遍历数组，每次先判断目标值与当前元素的差值，在hash表中是否已存在(表示存在于前面的数组元素中)。
若已存在，则取出对应元素的下标，并输出；若不存在，则将(元素，下标)的键值对存入hash表中。

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

另一种（不适用本题，因为排序后会改变下标）：
借用两个分别指向头尾的变量，每次判断变量所指位置数之和与目标值的大小，在进行判断前，需要对数组进行排序，使之成为一个升序数组（降序则将以下规则反转）。
若和小于目标值，说明需要增大加数，则令左指针右移；同理，若和大于目标值，则要减小加数，令右指针左移；直至和与目标值相等，输出指针所指元素。

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.

3Sum问题可以转化为2Sum问题：

a+b+c = t → a+b = t-c

外围循环遍历得c，循环内部为2Sum问题，寻找ab。

注意去重

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    for (int i = 0; i < nums.length-2; i++) {
        if (i != 0 && nums[i] == nums[i-1])
            continue;
        int left = i+1, right = nums.length-1;
        while (left < right) {
            if (nums[left] + nums[right] == -nums[i]) {
                list.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] < -nums[i])
                left++;
            else
                right--;
        }
    }
    return list;
}

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:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
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)

与3Sum同理。

public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    for (int i = 0; i < nums.length - 3; i++) {
        if (i != 0 && nums[i] == nums[i-1])
            continue;
        for (int j = i+1; j < nums.length - 2; j++) {
            if (j != i+1 && nums[j] == nums[j-1])
                continue;
            int left = j+1, right = nums.length-1;
            while(left < right) {
                if (nums[left] + nums[right] == target - nums[i] - nums[j]) {
                    list.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] < target - nums[i] - nums[j])
                    left++;
                else
                    right--;
            }
        }
    }
    return list;
}