Star

Leetcode 2Sum/3sum/4sum及其各种变体

Posted on | In |

经典的2sum，3sum，4sum极其变体题目总结，需要熟记。

Leetcode 1. Two Sum

Question:

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, and you may not use the same element twice.

Example: 

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Explanation:

用HashMap存差值，如果之后找到了立即返回两个index。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<nums.length; i++) {
        int minus = target - nums[i];
        if (map.containsKey(nums[i])) {
            result[1] = i;
            result[0] = map.get(nums[i]);
            break;
        } else {
            map.put(minus, i);
        }
    }
    return result;
}

Leetcode 167. Two Sum II - Input array is sorted

Question:

Given an array of integers that is already sorted in ascending order, 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 and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

Explanation:

Array是sorted，所以用两指针，找到符合条件的两个index。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] twoSum(int[] num, int target) {
    int[] result = new int[2];
    int left = 0;
    int right = num.length - 1;
    while (left < right) {
        int sum = num[left]+num[right];
        if (sum == target) {
            result[0] = left + 1;
            result[1] = right + 1;
            break;
        }
        else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return result;
}

Leetcode 170. Two Sum III - Data structure design

Question:

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure. find - Find if there exists any pair of numbers which sum is equal to the value. 

1
2
3
4
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Explanation:

一道典型的Trade off， 如果要add为O(n), 则find为 o(1),反之。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class TwoSum {
    /** Initialize your data structure here. */
    HashMap<Integer, Integer> map = new HashMap<>();
    public TwoSum() {
    }
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (map.containsKey(number)) {
            map.put(number, map.get(number)+1);
        } else {
            map.put(number, 1);
        }
    }
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for (int n:map.keySet()) {
            int minus = value -n;
            if (map.containsKey(minus)) {
                if (minus == n && map.get(n) > 1) return true;
                if (minus != n) return true;
            }
        }
        return false;
    }
}

Leetcode 15. 3Sum

Question:

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: The solution set must not contain duplicate triplets.

1
2
3
4
5
6
7
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Explanation:

先排序，遍历其中每个值，找到target减去后的值，按照two sum in sorted来做就行了。要注意skip相同值，不能重复放。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i=0; i<nums.length-2; i++) {
        if (i>0 && nums[i] == nums[i-1]) continue;
        int twoSum = 0 - nums[i];
        int left = i+1;
        int right = nums.length-1;
        while (left < right) {
            if (nums[left] + nums[right] == twoSum) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // skip the same ones
                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] < twoSum) {
                left ++;
            } else {
                right --;
            }
        }
    }
    return result;
}
}

Leetcode 16. 3Sum Closest

Question:

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. 

1
2
3
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).

Explanation:

同样的用3sum的方法做，只不过要多一个值来存储最小的diff和最靠近的sum。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int closest = target;
        int minDiff = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i=0; i<nums.length-2; i++) {
            int left = i+1; int right = nums.length-1;
            int twoSum = target - nums[i];
            System.out.println(closest);
            while (left < right) {
                int sum = nums[left] + nums[right];
                // if equal target, just return. Else find out the closest sum.
                if (twoSum == sum) {
                    return target;
                } else{
                    if (Math.abs(twoSum - sum) < minDiff) {
                        minDiff = Math.abs(twoSum - sum);
                        closest = sum+nums[i];
                    }
                    if (twoSum < sum) right--;
                    else left++;
                }
            }
        }
        return closest;
    }
}

Leetcode 259. 3Sum Smaller

Question:

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2: 

1
2
[-2, 0, 1]
[-2, 0, 3]

Explanation:

先排序，遍历其中每个值，找到target减去后的值，按照two sum in sorted来做就行了，但是要注意，因为只要算比它小的个数，所以注意指针如何移动，并且如何count。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int threeSumSmaller(int[] nums, int target) {
    int count = 0;
    Arrays.sort(nums);
    if (nums.length < 3) return 0;
    for (int i=0; i<nums.length; i++) {
        int twoSum = target - nums[i];
        int left = i+1; int right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] >= twoSum) {
                right --;
            } else {
                count += right - left;
                left ++;
            }
        }
    }
    return count;
}

Leetcode 18. 4Sum

Question:

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.

1
2
3
4
5
6
7
8
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]
]

Explanation:

在3Sum上面套一层就行了。吐槽无力。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    if (nums.length < 4) return list;
    Arrays.sort(nums);
    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; int 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;
}

Leetcode 454. 4Sum II

Question:

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

Explanation：

O(N^2)+Hashmap. Boring，下一题。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    HashMap<Integer,Integer> map = new HashMap<>();
    int count = 0;
    for (int i=0; i<A.length; i++) {
        for (int j=0; j<B.length; j++) {
            int sumAB = A[i] + B[j];
            if (!map.containsKey(0-sumAB)) map.put(0-sumAB, 1);
            else map.put(0-sumAB, map.get(0-sumAB)+1);
        }
    }
    for (int ii = 0; ii<C.length; ii++) {
        for (int jj=0; jj<D.length; jj++) {
            int sumCD = C[ii] + D[jj];
            if (map.containsKey(sumCD)) count+= map.get(sumCD);
        }
    }
    return count;
}