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

NO IMAGE

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.解題思路

題目要求兩個數和等於target,返回其index.題目說明不會有重複情況,所以我們一旦發現符合情況的,就可以直接結束迴圈並返回。
利用HashMap<nums[i],i>,邊遍歷儲存,邊尋找。當給定一個數n,只要看target-n是否在map中即可,如果存在,則取出其value – 即該數的下標。

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.解題思路

本題要求三個數的和為0,其實就是固定一個數n之後,找兩個數和為0-n,所以就轉化為求兩個數的和,那我們很容易想到使用二分法。
注意點:本題需要排除重複值,
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){
subres.add(0-target);
subres.add(nums[i]);
subres.add(nums[j]);
res.add(subres);
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;
res.addAll(threesum(target-nums[i],nums,i 1));
}
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;
res.addAll(twosum(target-nums[i],nums,i 1,first));
}
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){
subres.add(nums[first]);
subres.add(nums[second]);
subres.add(nums[i]);
subres.add(nums[j]);
res.add(subres);
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.解題思路

與3Sum相似,只不過本次是要尋找最接近target的3個數之和,我們需要維護minDiff和closetSum兩個變數。
但是本題題目說明不許考慮重複。 特殊情況就是sum正好等於target,那肯定是最接近的情況,直接返回即可。

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.解題思路

本題從1個陣列擴充套件到了4個陣列,求的是有多少組4數之和等於target的,我們把問題分為兩個數一組,假設當前兩個數A[i] B[j],那我們其實就是要在C和D中求是否存在和為0-A[i]-B[j],如果存在則返回存在的個數。想到用HashMap,儲存<sum,count>.

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