# [Leetcode] Two Sum, 3Sum,4Sum,4SumII,3Sum Closet

Two Sum
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.

``````Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0]   nums[1] = 2   7 = 9,
return [0, 1].
``````

1.解題思路

2.程式碼

``````public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res=new int[2];
if(nums.length==0) return res;
HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i  ){
int diff=target-nums[i];
if(hm.containsKey(diff)){
res[0]=i;
res[1]=hm.get(diff);
return res;
}
hm.put(nums[i],i);
}
return res;
}
}``````

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: 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]
]
``````

1.解題思路

1）固定的數下標為i,則要從i 1開始尋找後兩個數；
2）如果陣列中包含重複的數，則為了保證結果不出現重複，我們每次遇到重複的數需要跳過。

2.程式碼

``````public class Solution {
List<List<Integer>> res =new ArrayList<List<Integer>>();
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i  ){
if(i>0&&nums[i]==nums[i-1]) continue; //避免重複
twoSum(0-nums[i],nums,i 1,nums.length-1);
}
return res;
}
private void twoSum(int target,int[] nums, int start,int end){
int i=start,j=end;
while(i<j){
List<Integer> subres=new ArrayList<Integer>();
int sum=nums[i] nums[j];
if(sum==target){
do {
i  ;
}while(i < end && nums[i] == nums[i-1]);
do {
j--;
} while(j >= 0 && nums[j] == nums[j 1]);
}
else if(sum<target) i  ;
else j--;
}
}
}``````

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: 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]
]
``````

1.解題思路

4Sum,就是在3Sum基礎上再巢狀一層，注意點也是要避免重複。

2.程式碼

``````public class Solution {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
for(int i=0;i<nums.length-3;i  ){
if(i>0&&nums[i]==nums[i-1]) continue;
}
return res;
}
private List<List<Integer>> threesum(int target,int[] nums,int start){
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
int first=start-1;
for(int i=start;i<nums.length-1;i  ){
if(i>start&&nums[i]==nums[i-1]) continue;
}
return res;
}
private List<List<Integer>> twosum(int target,int[] nums,int start,int first){
List<List<Integer>> res =new ArrayList<List<Integer>>();
int second=start-1;
int i=start;
int j=nums.length-1;
while(i<j){
List<Integer> subres =new ArrayList<Integer>();
int sum=nums[i] nums[j];
if(sum==target){
i  ;
while(i<nums.length&&nums[i]==nums[i-1]){
i  ;
}
j--;
while(j>=0&&nums[j]==nums[j 1]){
j--;
}
}
else if(sum>target) j--;
else i  ;
}
return res;
}
}``````

3Sum Closest
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).``````

1.解題思路

2.程式碼

``````public class Solution {
public int threeSumClosest(int[] nums, int target) {
if(nums.length==0) return 0;
int minDiff=Integer.MAX_VALUE;
int closet=0;
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i  ){
int left=i 1;
int right=nums.length-1;
while(left<right){
int sum=nums[i] nums[left] nums[right];
int diff=Math.abs(sum-target);
if(diff<minDiff){
minDiff=diff;
closet=sum;
}
if(sum<target){
left  ;
}
else if(sum>target){
right--;
}
else return sum;
}
}
return closet;
}
}``````

4Sum II

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.

``````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
``````

1.解題思路

2.程式碼

``````public class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
if(A.length==0||B.length==0||C.length==0||D.length==0) return 0;
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
int count=0;
for(int i=0;i<A.length;i  ){
for(int j=0;j<B.length;j  ){
int sum=A[i] B[j];
if(map.containsKey(sum)){
map.put(sum,map.get(sum) 1);
}
else  map.put(sum,1);
}
}
for(int i=0;i<C.length;i  ){
for(int j=0;j<D.length;j  ){
int sum=0-C[i]-D[j];
if(map.containsKey(sum)){
count =map.get(sum);
}
}
}
return count;
}
}``````