在计算机领域,算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始,跟随我每天刷一道算法题吧!


在此之前,我们刷的几乎都是有关数组操作的算法题。在接下来的几天里,我们将学习 “双指针技巧”,它可以帮助我们解决许多与数组相关的问题。

双指针专题 第二天。

LeetCode #167 两数之和II

题目

给定一个已按照升序排列的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

说明:

  • 返回的下标值(index1 和 index2)不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例1:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 27 之和等于目标数 9 。因此 index1 = 1, index2 = 2

解题思路

思路:

#1 两数之和 不同的是,#167 两数之和II 输入的数组是已排序的。即索引递增,元素也递增;索引递减,元素也递减。
分别使用 index1、index2 指向数组的开头和结尾元素,计算两数之和。

  1. 若小于目标值,index1 递增。
  2. 若大于目标值,index2 递减。
  3. 若等于目标值,返回 index1+1 、index2+1。

双指针代码:

class Solution {
public int[] twoSum(int[] numbers, int target) {
// 左右指针
int index1 = 0;
int index2 = numbers.length - 1;
int sum = 0;

while(index1 < index2){
sum = numbers[index1]+numbers[index2];
if (sum == target){
return new int[]{index1 + 1 , index2 + 1};
}

// 小了,index1向右移;大了,index2向左移
if (sum < target)
index1++;
else
index2--;
}

return null;
}
}

评论