Problem Statement :-
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Example
Input : nums = [2,7,11,15], target = 9
Result : [0,1]
Explanation : Because nums[0] + nums[1] == 9, we return [0, 1].
Solution 1
we can solve this problem by using two pointer approach
lets discuss this solution step by step.
step-1 make a copy sortArr
array from the nums
array.
step-2 sort the copy sortArr
array.
step-3 initialise two pointers start=0
, end=n
.
step-4 run a loop from start
to end
and then,
1. calculate the
sum
fromstart
&end
indices of array.2. break the loop if
sum == target
3. increase the
start
by 1 ifsum < target
4. decrease the
end
by 1 ifsum > target
step-5 find the original indices from nums
array & return it.
Dry Run
nums = [1,3,5,2,7] , target = 4
1. copy the array.
copyArr = [1,3,5,2,7]
2. sort the copied array.
copyArr = [1,2,3,5,7]
3. run two pointers on sorted array
copyArr = [1,2,3,5,7]
| |
start end
sum = start + end
sum = 1 + 7 => 8
8 > target = 4 ----> end--
copyArr = [1,2,3,5,7]
| |
start end
sum = start + end
sum = 1 + 5 => 6
6 > target = 4 ----> end--
copyArr = [1,2,3,5,7]
| |
start end
sum = start + end
sum = 1 + 3 => 4
4 == target = 4 --> stop the loop
return the original indices of values from the nums
array.
0 1 2 3 4
copyArr = [1,2,3,5,7]
| |
start end
0 1 3 4 5
nums = [1,3,5,2,7]
ans = [0,1]
Java
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] sortArr = nums.clone();
int[] ans = new int[2];
Arrays.sort(sortArr);
int start =0, end = nums.length-1;
int n1 = 0,n2 = 0;
while(start < end){
int sum = sortArr[start] + sortArr[end];
if(sum == target) {
n1 = sortArr[start];
n2 = sortArr[end];
break;
}else
if(sum > target)
end--;
else
start++;
}
for(int i=0; i<nums.length; i++){
if(n1 == nums[i]){
ans[0] = i;
n1 = -1;
}
else
if(n2 == nums[i]){
ans[1] = i;
n2 = -1;
}}
return ans;
}
}
Top comments (0)