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};
    }
}

四、总结:

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


相关文章
|
25天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
12 0
|
26天前
|
算法
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
23 0
|
3月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
36 0
|
3月前
|
算法 Python
【Leetcode刷题Python】改进的算法,高效求一个数的因子
一个高效的Python函数用于找出一个整数的所有因子,通过仅遍历到该数平方根的范围来优化性能。
37 0
|
5月前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
5月前
|
算法
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
|
15天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。