Two pointers
Two sum
- Problem: Given a sorted array of integers and a target sum, find two numbers such that their sum equals the target.
- Example:
Input: nums = [2, 7, 11, 15], target = 9.Output: [1, 2](1-based indexing).
Two Pointers Approach:
- Initialize Two Pointers: One pointer (
left) starts at the beginning of the array, and the other (right) starts at the end. - Iterate and Compare:
- Calculate the sum of the elements at both pointers (
nums[left] + nums[right]). - If the sum equals the target, return the indices.
- If the sum is less than the target, move the
leftpointer to the right (left++) to increase the sum. - If the sum is greater than the target, move the
rightpointer to the left (right--) to decrease the sum.
- Calculate the sum of the elements at both pointers (
- Stop when they cross each other: The loop ends when
leftis no longer less thanright.
public int[] twoSum(int[] nums, int target) {
int left = 0; // Start of the array
int right = nums.length - 1; // End of the array
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[] {left + 1, right + 1}; // 1-based indexing
} else if (sum < target) {
left++; // Move left pointer to the right
} else {
right--; // Move right pointer to the left
}
}
return new int[] {}; // Return an empty array if no solution found
}
