20天算法刷题计划-两数之和 II - 输入有序数组

简介: 这题其实还挺简单的,双循环的暴力解法谁都能想到,上面只写了一种解法,还有许多其他的方法,但是想到的还是上面这种方法,也没有很麻烦。想看看其他思路可以去题目的题解和评论区看看其他大佬的解法,了解下思路也好

一、题目描述:

给你一个下标从 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.下标从 1 开始的整数数组 ,不是从0开始的下标

  1. 非递减顺序排列
  2. 仅存在一个有效答案

看完示例,最先想到的双重for循环,可以的得到答案,但是认真分析完题目要求,因为题目中说明了市一个非递减顺序排列的数组,并且只存在一个答案,以及题目分类属于双指针,采用双指针思路思考更好些。解题思路如下:

设定left ,right 两个指针,分别指向数组的头和尾,因为市非递减且只存在一个答案,

当num[left]+num[right]>target 时,right 向左移动,

当num[left]+num[right]<target 时,left 向右移动,

直到num[left]+num[right]=target时,left 和right指向即为结果。

同时注意到下标从 1 开始 ,返回时需要将left 和right 加1.

三、AC 代码:

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

四、总结:

这题其实还挺简单的,双循环的暴力解法谁都能想到,上面只写了一种解法,还有许多其他的方法,但是想到的还是上面这种方法,也没有很麻烦。想看看其他思路可以去题目的题解和评论区看看其他大佬的解法,了解下思路也好


目录
打赏
0
0
0
0
4
分享
相关文章
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
40 0
|
4月前
|
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
54 0
|
6月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
6月前
|
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
74 0
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
65 0
|
6月前
|
【Leetcode刷题Python】改进的算法,高效求一个数的因子
一个高效的Python函数用于找出一个整数的所有因子,通过仅遍历到该数平方根的范围来优化性能。
56 0
|
8月前
|
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
8月前
|
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
基于GA遗传算法的多机无源定位系统GDOP优化matlab仿真
本项目基于遗传算法(GA)优化多机无源定位系统的GDOP,使用MATLAB2022A进行仿真。通过遗传算法的选择、交叉和变异操作,迭代优化传感器配置,最小化GDOP值,提高定位精度。仿真输出包括GDOP优化结果、遗传算法收敛曲线及三维空间坐标点分布图。核心程序实现了染色体编码、适应度评估、遗传操作等关键步骤,最终展示优化后的传感器布局及其性能。
基于深度学习的路面裂缝检测算法matlab仿真
本项目基于YOLOv2算法实现高效的路面裂缝检测,使用Matlab 2022a开发。完整程序运行效果无水印,核心代码配有详细中文注释及操作视频。通过深度学习技术,将目标检测转化为回归问题,直接预测裂缝位置和类别,大幅提升检测效率与准确性。适用于实时检测任务,确保道路安全维护。 简介涵盖了算法理论、数据集准备、网络训练及检测过程,采用Darknet-19卷积神经网络结构,结合随机梯度下降算法进行训练。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等