LeetCode: 167. 两数之和 II - 输入有序数组 | 双指针专题

简介: LeetCode: 167. 两数之和 II - 输入有序数组 | 双指针专题

image.png

🚩 题目链接

⛲ 题目描述

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 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 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

🌟 求解思路&实现代码&运行结果


⚡ 双指针

🥦 求解思路

  1. 首先我们要先弄明白题目的意思,抓住解题的关键点,暴力解法可以想到,但是时间超限,不能通过,我们就需要利用数组有序的这个特性+双指针来求解。
  2. 初始两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和,并和目标值比较。
  3. 如果两个元素之和等于目标值,则发现了唯一解。
  4. 如果两个元素之和小于目标值,则将左侧指针右移一位。
  5. 如果两个元素之和大于目标值,则将右侧指针左移一位。
  6. 移动指针之后,重复上述操作,直到找到答案。
  7. 有了基本的思路,接下来我们就来通过代码来实现一下。

    🥦 实现代码

    class Solution {
         
         
     public int[] twoSum(int[] numbers, int target) {
         
         
         int n=numbers.length;
         int left=0,right=n-1;
         while(left<right){
         
         
             if(numbers[left]+numbers[right]>target){
         
         
                 right--;
             }else if(numbers[left]+numbers[right]<target){
         
         
                 left++;
             }else{
         
         
                 return new int[]{
         
         left+1,right+1};
             }
         }
         return new int[]{
         
         };
     }
    }
    

🥦 运行结果

时间复杂度&空间复杂度

image.png

相关文章
|
2天前
|
存储 搜索推荐
题目----力扣--合并两个有序数组
题目----力扣--合并两个有序数组
8 0
|
3天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
10 0
|
7天前
|
算法
[优选算法]——双指针——Leetcode——1089. 复写零
[优选算法]——双指针——Leetcode——1089. 复写零
|
7天前
|
算法
【优选算法】——双指针——Leetcode——283.移动零
【优选算法】——双指针——Leetcode——283.移动零
|
8天前
|
存储 搜索推荐 C语言
Leetcode—合并两个有序数组—C语言
Leetcode—合并两个有序数组—C语言
|
15天前
|
索引
LeetCode438题(无敌双指针——滑动窗口)
LeetCode438题(无敌双指针——滑动窗口)
|
15天前
leetcode代码记录(两数之和
leetcode代码记录(两数之和
15 1
|
15天前
|
算法 C语言 C++
|
15天前
leetcode代码记录(有序数组的平方
leetcode代码记录(有序数组的平方
13 0
|
15天前
leetcode代码记录(有序数组两数之和
leetcode代码记录(有序数组两数之和
18 0