力扣算法打卡刷题|??导图整理数组3: 两数之和II有序数组, 多个有序, 思路全变, 力扣167?? 两数之和|有序数组|力扣算法

此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.
目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).
关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接. 导图中源码在文章最后.
博主在公众号 [一起学计算机]每日首发力扣算法, 欢迎关注公众号每日和博主一起打卡刷题!
博主在 B站同步更新了算法视频讲解和其他文章/导图讲解, 更易于理解, 欢迎来看!

目录
【力扣算法打卡刷题|??导图整理数组3: 两数之和II有序数组, 多个有序, 思路全变, 力扣167??】0.导图整理
1.两数之和中有序和无序的区别
2.二分法和寻找插入位置的区别
3.双指针思想
源码
题目链接: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
0.导图整理

文章图片

1.两数之和中有序和无序的区别之前写了一篇关于无序数组的两数之和问题, 在无序数组中寻找第二个数就没有多少捷径, 毕竟数组无序, 很多经典的方法都用不上, 最后只能牺牲空间来换取时间, 利用哈希表将空间复杂度增加到了O(n), 从而降低了寻找第二个数的时间复杂度.
但是当数组有序之后, 就能使用一些经典的算法同时仍然保证空间复杂度为O(1), 不需要牺牲空间来换取时间, 比如下面马上介绍的二分法和双指针方法.
这里给我们提供了一种思维, 那我们是不是也可以将无序数组先进行排序后, 再使用这些经典算法呢? 当然可以这么做, 但对于两数之和来说, 必要性不是太大. 因为最快的排序算法也需要O(nlogn)的时间复杂度, 对于两数之和确实提升也不是太大, 但是对于三数之和/四数之和还是挺实用的, 后续文章将很快讲到.
2.二分法和寻找插入位置的区别数组有序了, 使用二分法寻找第二个数就可以将时间复杂度降到O(logn)了, 关于二分法, 之前的这篇文章已经讲解的很清楚了, 这里就不再重复介绍了.
这里说说二分法和寻找插入位置的不同, 也是两篇文章中代码不同的部分.
寻找插入位置最终无论是否找到目标值, 返回的位置结果都是相同的, 而且题中说明数组中无重复元素, 保证了返回位置的唯一性, 所以最终 left == right == mid, 返回哪个都无所谓, 也并不需要特殊的将等于目标值这个情况单独写出来, 所以代码只讨论了两种情况, 最终一个返回值, 非常简洁.
但是对于本题使用的二分法, 首先并没有要求数组无重复元素, 其次, 我们要的是具体的等于目标值的位置, 并不是寻找插入位置, 所以在找不到的情况下, 我们只能返回 [-1, -1], 首先的返回结果就有了两种情况.
其次由于有重复元素的存在, 若直接使用之前的只讨论两种情况的二分法是会出错的, 这里必须要讨论三种情况, 且在相等的情况下直接返回正确的结果, 在找不到的情况下返回 [-1, -1].
本题另外的一个小的注意点是: 返回的下标从1开始, 只要在原本的返回结果上+1就可以了.
还有一个注意点是, 为了避免重复寻找,在寻找第二个数时,只在第一个数的右侧寻找, 也就是left = i+1.
3.双指针思想双指针在有序数组中是非常重要的思想, 一定要掌握. 思想还是挺简单的, 但是优化的效果是非常棒的, 比二分法更加优秀. 导图中对思想的描述挺清楚了, 这里说下它的适用范围吧.
最基本最首要的前提是数组一定要是有序的, 其次, 一定要涉及到几个数之间的相互关系, 最常用的也就是几个数相加等于某一定值的情况, 其他情况, 今后遇到了再细说. 常用于数组和链表之中.
源码Python:

# 二分法 class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: n = len(numbers) for i in range(n): left, right = i+1, n# 采用左闭右开区间[left,right),left+1避免重复 while left < right: # 右开所以不能有=,区间不存在 mid = (right - left) // 2 + left # 防止溢出 if numbers[mid] == target - numbers[i]: # 数组中存在重复元素,必须判断相等 return [i + 1, mid + 1] # 返回的下标从1开始,都+1 elif numbers[mid] > target - numbers[i]: right = mid # 右开,真正右端点为mid-1 else: left = mid + 1 # 左闭,所以要+1return [-1, -1]# 双指针 class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: low, high = 0, len(numbers) - 1 # 确定两个指针的位置 while low < high: # 指针移动条件 total = numbers[low] + numbers[high] if total == target: return [low + 1, high + 1] # // 返回下标从1开始 elif total < target: low += 1 # Python中没有++ --的用法 else: high -= 1return [-1, -1]

java:

// 二分法 class Solution { public int[] twoSum(int[] numbers, int target) { for (int i = 0; i < numbers.length; ++i) { int left = i+1, right = numbers.length; // 采用左闭右开区间[left,right),left+1避免重复 while (left < right) {// 右开所以不能有=,区间不存在 int mid = (right - left) / 2 + left; // 防止溢出 if (numbers[mid] == target - numbers[i]) { // 数组中存在重复元素,必须判断相等 return new int[]{i + 1, mid + 1}; // 返回的下标从1开始,都+1 } else if (numbers[mid] > target - numbers[i]) { //中点大于目标值,在左侧 right = mid; // 右开,真正右端点为mid-1 } else { left = mid + 1; //左闭,所以要+1 } } } return new int[]{-1, -1}; } }// 双指针 class Solution { public int[] twoSum(int[] numbers, int target) { int low = 0, high = numbers.length - 1; // 确定两个指针的位置 while (low < high) { // 指针移动条件 int sum = numbers[low] + numbers[high]; if (sum == target) { return new int[]{low + 1, high + 1}; // 返回下标从1开始 } else if (sum < target) { ++low; } else { --high; } } return new int[]{-1, -1}; } }

感觉作者写的不错的, 别忘了点赞关注加收藏哦(一键三连)!你的支持会带给我极大的动力, 写出更多优秀文章!

文章图片

文章到这里就结束了, 感谢你的认真观看, 为了感谢读者们, 我把我一直以来整理的各种计算机相关/考研相关精品思维导图/力扣算法讲解/面试资料/各种实用软件工具分享给大家(并且会持续更新哦!), 希望能够帮助到你们.
关注公众号 [一起学计算机] 点击资源获取即可获得所有资源, 包含的资源如下图, 其中具体资源的相关讲解和各种软件的使用可以查看下面相应的文章.

文章图片

文章图片

我的更多精彩文章链接, 欢迎查看
各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)
力扣算法刷题根据思维导图整理笔记快速记忆算法重点内容(可在公众号和博主一起打卡学习哦)

经典动漫全集目录 精彩剧集
海贼王动漫全集目录分章节精彩打斗剧集思维导图整理
火影忍者动漫全集目录分章节精彩打斗剧集思维导图整理
死神动漫全集目录分章节精彩打斗剧集思维导图整理

计算机专业知识 思维导图整理
最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)
最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目
最值得收藏的计算机网络全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介
最值得收藏的算法分析与设计全部知识点思维导图整理(北大慕课课程)
最值得收藏的数据结构全部知识点思维导图整理(王道考研), 附带经典题型整理
最值得收藏的人工智能导论全部知识点思维导图整理(王万良慕课课程)
最值得收藏的数值分析全部知识点思维导图整理(东北大学慕课课程)
最值得收藏的数字图像处理全部知识点思维导图整理(武汉大学慕课课程)
红黑树一张导图解决红黑树全部插入和删除问题包含详细操作原理情况对比
各种常见排序算法的时间/空间复杂度是否稳定算法选取的情况改进思维导图整理

人工智能课件算法分析课件Python课件数值分析课件机器学习课件图像处理课件

考研相关科目 知识点 思维导图整理
考研经验--东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)
东南大学软件工程 906 数据结构 C++ 历年真题思维导图整理
东南大学软件工程复试3门科目历年真题思维导图整理
最值得收藏的考研高等数学全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理
最值得收藏的考研线性代数全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理
高等数学中值定理一张思维导图解决中值定理所有题型
考研思修知识点做题技巧同类比较重要会议 1800易错题思维导图整理
考研近代史知识点做题技巧同类比较重要会议 1800易错题思维导图整理
考研马原知识点做题技巧同类比较重要会议 1800易错题思维导图整理

考研数学课程笔记考研英语课程笔记考研英语单词词根词缀记忆考研政治课程笔记

Python相关技术知识点思维导图整理
Numpy常见用法全部OneNote笔记全部笔记思维导图整理
Pandas常见用法全部OneNote笔记全部笔记思维导图整理
Matplotlib常见用法全部OneNote笔记全部笔记思维导图整理
PyTorch常见用法全部OneNote笔记全部笔记思维导图整理
Scikit-Learn常见用法全部OneNote笔记全部笔记思维导图整理

Java相关技术/ssm框架全部笔记
SpringspringmvcMybatisjsp

科技相关 小米手机
小米红米历代手机型号大全发布时间发布价格
常见手机品牌的各种系列划分及其特点
历代CPU和GPU的性能情况和常见后缀的含义思维导图整理