【LC总结】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

摘要：找符合条件的总数。双指针区间考虑边界，长度，为空，等。之后的范围用双指针和表示。若三个指针的数字之和为，加入结果数组。不要求，所以不用判断了。同理，头部两个指针向后推移，后面建立左右指针夹逼，找到四指针和为目标值的元素。

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

numbers=[2, 7, 11, 15], target=9

return [1, 2]

Either of the following solutions are acceptable:

O(n) Space, O(nlogn) Time
O(n) Space, O(n) Time

需要返回的是index，不能重新sort，所以，不能用双指针法，尽量用HashMap做。

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = {-1, -1};
        if (numbers.length < 2) return res;
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i+1; j < numbers.length; j++) {
                if (numbers[i]+numbers[j] == target) {
                    res[0] = i+1;
                    res[1] = j+1;
                    return res;
                }
            }
        }
        return res;
    }
}

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

Given an array of integers, find how many pairs in the array such that their sum is bigger than a specific target number. Please return the number of pairs.

Given numbers = [2, 7, 11, 15], target = 24. Return 1. (11 + 15 is the only pair)

Do it in O(1) extra space and O(nlogn) time.

找符合条件的pair总数。
Key:

双指针

区间

public class Solution {
    public int twoSum2(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;
        Arrays.sort(nums);
        int count = 0;
        int left = 0, right = nums.length-1;
        while (left < right) {
            if (nums[left]+nums[right] > target) {
                count += right-left;
                right--;
            } else {
                left++;
            }
        }
        return count;
    }
}

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.

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.

For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:

(-1, 0, 1)
(-1, -1, 2)

考虑边界，长度<3，为空，等。
对给定数组排序。
定一个指针i，从头开始循环推进。若重复，则跳过。
i之后的范围用双指针left和right表示。
若三个指针的数字之和为0，加入结果数组。双指针继续移动，若重复，则跳过。
若三个指针的数字之和小于0，左指针后移。
若三个指针的数字之和大于0，右指针前移。

public class Solution {
    public ArrayList> threeSum(int[] A) {
        ArrayList> res = new ArrayList();
        if (A.length < 3) return null;
        Arrays.sort(A);
        for (int i = 0; i <= A.length-3; i++) {
            int left = i+1, right = A.length-1;
            if (i != 0 && A[i] == A[i-1]) continue;
            while (left < right) {
                int sum = A[i]+A[left]+A[right];
                if (sum == 0) {
                    ArrayList temp = new ArrayList();
                    temp.add(A[i]);
                    temp.add(A[left]);
                    temp.add(A[right]);
                    res.add(temp);
                    left++;
                    right--;
                    while (left < right && A[left] == A[left-1]) left++;
                    while (left < right && A[right] == A[right+1]) right--;
                }
                else if (sum < 0) left++;
                else right--;
            }
        }
        return res;
    }
}

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).

O(n^2) time, O(1) extra space

不要求unique triplets，所以不用判断duplicate了。
定指针i从数组头部向后推移，在i的右边建立左右指针left和right，计算三指针和。
用左右指针夹逼找和的最小值并更新。

public class Solution {
    public int threeSumClosest(int[] A ,int target) {
        int min = Integer.MAX_VALUE - target;
        if (A == null || A.length < 3) return -1;
        Arrays.sort(A);
        for (int i = 0; i < A.length-2; i++) {
            int left = i+1, right = A.length-1;
            while (left < right) {
                int sum = A[i]+A[left]+A[right];
                if (sum == target) return sum;
                else if (sum < target) left++;
                else right--;
                min = Math.abs(min-target) < Math.abs(sum-target) ? min : sum;
            }
        }
        return min;
    }
}

Description
Notes
Testcase
Judge
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.

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.

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)

同理，头部两个指针向后推移，后面建立左右指针夹逼，找到四指针和为目标值的元素。

public class Solution {
    public ArrayList> fourSum(int[] A, int target) {
        int n = A.length;
        ArrayList> res = new ArrayList();
        Arrays.sort(A);
        for (int i = 0; i < n-3; i++) {
            if (i != 0 && A[i] == A[i-1]) continue;
            for (int j = i+1; j <= n-3; j++) {
                if (j != i+1 && A[j] == A[j-1]) continue;
                int left = j+1, right = n-1;
                while (left < right) {
                    int sum = A[i]+A[j]+A[left]+A[right];
                    if (sum == target) {
                        ArrayList temp = new ArrayList();
                        temp.add(A[i]);
                        temp.add(A[j]);
                        temp.add(A[left]);
                        temp.add(A[right]);
                        res.add(temp);
                        left++;
                        right--;
                        while (left < right && A[left] == A[left-1]) left++;
                        while (left < right && A[right] == A[right+1]) right--;
                    }
                    else if (sum < target) left++;
                    else right--;
                }
            }
        }
        return res;
    }
}