M

1533626601

tags: Hash Table

#### Based on 2sum

- 1. 利用2Sum的原理，把4Sum分为连个2Sum。左一个pair,右一个pair，每个pair里面放2个数字。

- 2. 以一个点，i，作为分界口，也要列举出所有i之前的pair,作为基础。

- 3. 再尝试从所有i+1后面,找合适的2nd pair。

- Time: O(n^2 * x), where x = # of candidates, still slow

- 可以用HashSet<List>, 可以直接比较list里面每一个元素, 保证set不重复.

- Previous Notes: 在造class Pair时候，要做@override的function: hashCode(), equals(Object d). 平时不太想得起来用。

- 参见 http://lifexplorer.me/leetcode-3sum-4sum-and-k-sum/

#### Based on 3Sum

- 3Sum外面再加一层. 参考3Sum. 时间O(n^3)。 但此方法在k-sum时候，无疑过于费时间. O(n^k)

```

/*

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.

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)

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.

Tags Expand

Two Pointers Sort Hash Table Array

*/

/*

Thoughts:

Can't do for loop over 3sum, which is O(n^3), not doable.

We can break the nums into 2 major parts by index i.

1st part: from [0 ~ i], we'll try all possible ways to pair [x, i] and store the sum of nums[x]+nums[i] in map.

Note: key is sum, and the value is a hashSet of ArrayList. Where the hashset has itself functions to tell duplicate of pairs.

2nd part: try [i + 1, end], see if any combination sum that makes: target - sum exist in map. -> becomes same old 2sum problem.

O(n)

*/

/**

Why having below front-pair-building after previous for end-pair-checking for loop?

Here: we build [0 ~ i], and in next round, when we processs [i + 1, end], pairs built among [0~i] below will all be used.

Rather: if we have lift the for loop below to calculate [0~i] before the end-pair-checking of same [i~end],

there is one index at [i] will overlap, which turns to be incorrect.

Therefore, we build front-pairs aftwarwards: it's building [0~i] here, which aims to help next round of end-pair-checking on [i+1, end].

*/

class Solution {

public List<List<Integer>> fourSum(int[] nums, int target) {

List<List<Integer>> result = new ArrayList<>();

if (nums == null || nums.length <= 3) return result;

int n = nums.length;

Arrays.sort(nums);

Map<Integer, HashSet<List>> map = new HashMap<>();

Set<String> cache = new HashSet<>();

for (int i = 0; i < n; i++) {

// Check if [i + 1, end] can be added up to target

for (int k = i + 1; k < n; k++) {

int sum = nums[i] + nums[k];

if (map.containsKey(target - sum)) {// Try to match up the 4 pairs

for (List<Integer> frontPair : map.get(target - sum)) {

List<Integer> list = Arrays.asList(frontPair.get(0), frontPair.get(1), nums[i], nums[k]);

String key = buildKey(list);

if (!cache.contains(key)) {

result.add(list);

cache.add(key);

}

}

}

}

// Build up the pair from [0 ~ i]

for (int j = 0; j < i; j++) {

int sum = nums[j] + nums[i];

map.putIfAbsent(sum, new HashSet<>());

map.get(sum).add(Arrays.asList(nums[j], nums[i]));

}

}

return result;

}

private String buildKey(List<Integer> list) {

StringBuffer sb = new StringBuffer();

for (int num : list) sb.append(num + "@");

return sb.toString();

}

}

/*

Thoughts

Perform another layer outside of 3SUM. O(n^3).

Note: If try to divide and perform two 2SUM, it will be a bit difficult. Refer to http://blog.csdn.net/linhuanmars/article/details/24826871

*/

public class Solution {

public ArrayList<ArrayList<Integer>> fourSum(int[] numbers, int target) {

ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();

if(numbers == null || numbers.length < 4) {

return rst;

}

Arrays.sort(numbers);

//Pick 1st element

for (int i = 0; i < numbers.length - 3; i++) {

if (i != 0 && numbers[i] == numbers[i - 1]) {//Check for duplicate of 1st element

continue;

}

//Pick 2nd element

for (int j = i + 1; j < numbers.length - 2; j++) {

if (j != i + 1 && numbers[j] == numbers[j - 1]) {//Check for duplicate of 2nd element

continue;

}

//Pick 3rd and 4th element

int third = j + 1;

int fourth = numbers.length - 1;

while (third < fourth) {

int sum = numbers[i] + numbers[j] + numbers[third] + numbers[fourth];

if (sum < target) {

third++;

} else if (sum > target) {

fourth--;

} else {//sum == target

ArrayList<Integer> list = new ArrayList<Integer>();

list.add(numbers[i]);

list.add(numbers[j]);

list.add(numbers[third]);

list.add(numbers[fourth]);

rst.add(list);

third++;

fourth--;

while (third < fourth && numbers[third] == numbers[third - 1]) {

third++;

}

while (third < fourth && numbers[fourth] == numbers[fourth + 1]){

fourth--;

}

}

}

}

}

return rst;

}

}

/*

NOT Complete yet. Has a order issue in HashSet

http://lifexplorer.me/leetcode-3sum-4sum-and-k-sum/

Thoughts:

Utilize 2Sum.

Notes 2017: no need to create a new class Pair. We can just use list in HashSet<List>, which compairs the list element and eleminate duplicated list.

*/

public class Solution {

//Create class Pair for HashSet<Pair> to use

class Pair {

Integer x;

Integer y;

public Pair(int x, int y){

this.x = x;

this.y = y;

}

@Override

public int hashCode(){

return this.x.hashCode() + this.y.hashCode();

}

@Override

public boolean equals(Object d) {

if (!(d instanceof Pair)) {

return false;

}

Pair p = (Pair)d;

return (this.x == p.x) && (this.y == p.y);

}

}

public ArrayList<ArrayList<Integer>> fourSum(int[] numbers, int target) {

ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();

if (numbers == null || numbers.length < 4) {

return rst;

}

Arrays.sort(numbers);

HashMap<Integer, HashSet<Pair>> map = new HashMap<Integer, HashSet<Pair>>();

for (int i = 0; i < numbers.length; i++) {

for (int j = i + 1; j < numbers.length; j++) {

int sum = numbers[i] + numbers[j];

if (map.containsKey(target - sum)) {

for (Pair p : map.get(target - sum)) {

ArrayList<Integer> list = new ArrayList<Integer>();

list.add(p.x);

list.add(p.y);

list.add(numbers[i]);

list.add(numbers[j]);

if (!rst.contains(list)) {

rst.add(list);

}

}

}

}

//Add all pairs up to i

for (int j = 0; j < i; j++) {

int sum = numbers[i] + numbers[j];

if (!map.containsKey(sum)) {

map.put(sum, new HashSet<Pair>());

}

map.get(sum).add(new Pair(numbers[j], numbers[i]));

}

}

return rst;

}

}

```