这段代码实现了在一个非递减排序的数组中找到两个数,使它们的和等于目标值的算法。算法使用了双指针技术,具体思想如下:
算法思想:
-
初始化指针:定义两个指针
left
和right
,分别指向数组的起始位置和末尾位置。left
从左向右遍历,right
从右向左遍历。 -
计算当前和:
- 在循环中,每次计算
numbers[left]
和numbers[right]
的和,记为sum
。
- 在循环中,每次计算
-
判断是否满足目标值:
- 如果
sum
等于目标值target
,则找到了符合条件的两个数,此时返回它们的索引(题目要求索引从1开始,所以要将数组下标left
和right
各加1)。 - 如果
sum
小于目标值target
,说明需要更大一点的数才能达到目标值,因此将left
指针向右移动一位,以增加sum
。 - 如果
sum
大于目标值target
,说明需要更小一点的数才能达到目标值,因此将right
指针向左移动一位,以减小sum
。
- 如果
-
返回结果:
- 如果在循环结束后没有找到符合条件的两个数,返回一个空数组(虽然根据题目描述,总会有一个解,因此这一步通常不会被执行)。
时间复杂度
该算法的时间复杂度是 (O(n)),因为每次循环中指针 left
或 right
都会向中间移动,最多需要遍历整个数组一次。
总结
此算法利用了数组的有序性,通过双指针逐步逼近目标值,避免了暴力解法的多重循环,从而提升了效率。
java solution
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
int sum = 0;
int[] result = new int[2];
while(left != right) {
sum = numbers[left] + numbers[right];
if(sum == target) {
result[0] = left + 1;
result[1] = right + 1;
return result;
}else if(sum < target) {
left++;
} else {
right--;
}
}
return new int[] {};
}
}