📝个人主页:五敷有你
🔥系列专栏:算法分析与设计
⛺️稳中求进,晒太阳
题目
示例
示例 1:
输入:numbers = [2,7,11,15], target = 9 输出:[1,2] 解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2:
输入:numbers = [2,3,4], target = 6 输出:[1,3] 解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3:
输入:numbers = [-1,0], target = -1 输出:[1,2] 解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
思路(双指针)
双指针是一种常用的算法技巧,通常用于数组或链表等数据结构的遍历和搜索。它的基本思想是使用两个指针在数据结构上同时移动,以解决一些特定问题。
常见的双指针模式有两种:快慢指针和左右指针。
-
快慢指针:
- 适用于解决链表中的问题,如判断链表是否有环、找到链表的中间节点等。
- 一般情况下,两个指针以不同的速度移动,例如快指针每次移动两步,慢指针每次移动一步。
- 当两个指针相遇时,可以得出一些结论,比如链表中存在环。
-
左右指针:
- 适用于解决数组或字符串中的问题,如在有序数组中找到两个数的和等于目标值、反转数组等。
- 一般情况下,两个指针分别从数组的两端开始移动。
- 根据问题的特点,通过调整指针的移动方式,可以高效地解决问题。
在数组中找两个数的和等于目标值的问题中,就可以使用左右指针的方法。一般步骤如下:
-
初始化两个指针,一个指向数组的起始位置,另一个指向数组的末尾。
-
在每一步迭代中,计算指针所指元素的和。
-
如果和等于目标值,找到了答案,返回相应的结果。
-
如果和小于目标值,将左指针向右移动一位,以增大和。
-
如果和大于目标值,将右指针向左移动一位,以减小和。
-
重复步骤2-5,直到找到答案或者指针相遇。
双指针技巧在解决一些搜索、遍历、判断问题时具有很高的效率,能够将时间复杂度降低到线性级别。
算法分析与设计
代码实现
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int currentSum = numbers[left] + numbers[right];
if (currentSum == target) {
return new int[]{left + 1, right + 1}; // 返回下标(注意下标是从1开始的)
} else if (currentSum < target) {
left++;
} else {
right--;
}
}
// 如果没有找到满足条件的两个数,返回空数组或者其他指定的值
return new int[]{};
}
}
运行结果
这个算法的时间复杂度是 O(n),其中 n 是数组的长度。