摘要：找符合條件的總數。雙指針區間考慮邊界，長度，為空，等。之后的范圍用雙指針和表示。若三個指針的數字之和為，加入結果數組。不要求，所以不用判斷了。同理，頭部兩個指針向后推移，后面建立左右指針夾逼，找到四指針和為目標值的元素。

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