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. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
Solution
Two Pointer Solution: First copy numbers[] into old[] and sort old[]. Then we use two pointers to scan for the target sum. At last, we recover the indexes of these two elements in the unsorted array. This takes O(nlogn) time.
During one pass, we put element and index (as key, value) into the map, meanwhile we search for target-num[i] in our map. If found, get the two indexes. This takes O(n) time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
publicint[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int n = numbers.length;
int[] result = newint[2];
for (int i = 0; i < numbers.length; i++)
{
if (map.containsKey(target - numbers[i]))
{
result[0] = map.get(target-numbers[i]) + 1;
result[1] = i + 1;
break;
}
else
{
map.put(numbers[i], i);
}
}
return result;
}
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: 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)
Solution
Brute force method. Use three loops, for each i,j,k indexes check if 3 sum equals to 0. In order to avoid duplicate sets, we make the following obeservations:
The first element must be non-positive
Given the first element, the first two element must sum to non-positive
Note: the Solution doesn’t handle duplicates, and O(N^3) exceeded limited time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> res= new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> each=new ArrayList<Integer>();
for (int i=0;i<num.length;i++){
if(num[i]>0) break;
for (int j=i;j<num.length;j++){
if(num[i]+num[j]>0) break;
for(int k=j;k<num.length;k++){
if(num[i]+num[j]+num[k]==0){
each.add(num[i]);
each.add(num[j]);
each.add(num[k]);
res.add(each);
each.clear();
}
}
}
}
return res;
}
Better Solution:
Similar to how we used 2 pointers in 2Sum, we now use three pointers to solve 3Sum. For removing duplicate sets, we first sort input.
For the first element, we only run checking process for the first of duplicate elements.
We use two pointers to check for cases such that num[i]+num[l]+num[r]==0. If found, move both pointers closer (don’t forget to skip duplicates), if not found, move only one pointer.
Overall runtime is O(N^2) and we can guarantee no duplicate sets.
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
32
33
34
35
36
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> res= new ArrayList<ArrayList<Integer>>();
int l=0,r=0;
for (int i=0;i<num.length-2;i++){
if(num[i]>0) break;
//skip the duplicated first element
elseif(i>0 && num[i]==num[i-1]) continue;
l=i+1;
r=num.length-1;
//use left and right pointer to scan the rest
while(l<r){
if(num[i]+num[l]+num[r]==0){
ArrayList<Integer> tmp=new ArrayList<Integer>();
tmp.add(num[i]);
tmp.add(num[l]);
tmp.add(num[r]);
res.add(tmp);
l++;
r--;
//skip duplicates
while(l<r && num[l]==num[l-1]) l++;
while(l<r && num[r]==num[r+1]) r--;
}
//scan the rest starting with num[i]
elseif(num[i]+num[l]+num[r]<0) l++;
else r--;
}
}
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).
Similar to 3Sum, first sort the array and then we use three pointers to scan for the closest sum:
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
publicintthreeSumClosest(int[] num, int target) {
int cls=Integer.MAX_VALUE,res=Integer.MAX_VALUE;
int l=0,r=0;
int[] newnum = newint[num.length];
System.arraycopy(num, 0, newnum, 0, num.length);
Arrays.sort(newnum);
for(int i=0;i<num.length;i++){
l=i+1; r=num.length-1;
while(l<r){
int sum=newnum[i]+newnum[l]+newnum[r];
int diff=Math.abs(target-sum);
//if match found, immediately return sum
if(diff==0) return sum;
//check if current cls is min, update sum
elseif (diff<cls){
cls=diff;
res=sum;
}
//move pointers accordingly
elseif(sum-target<=0) l++;
else {r--;}
}
}
return res;
}
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: 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. 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)
Solution
similar to 3sum, use to pointer to find quadruplets faster, O(n^3) time.
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
32
33
34
35
36
37
38
publicstatic List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<List<Integer>>();
for(int i=0; i<nums.length-3; i++){
if (i > 0 && nums[i] == nums[i-1]) //remove duplicates
continue;
for(int j=i+1; j<nums.length-2; j++){
if (j>i+1 && nums[j]==nums[j-1]) //remove duplicates
