摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.
目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).
关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接.
想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法! 博主同步更新了算法视频讲解, 更易于理解, 不想看文章的 欢迎来看!
关注博主获得题解更新的最新消息!!!
原本在整理 n数之和 系列时是没有整理此题的, 后来在重看 三数之和 时, 发现了这样的评论: 百度一面题目: 找三数和最接近0, 只要将此题中的target设置0即可, 所以又重新补充了此题!
本题是 三数之和 的进阶版, 在思想上和 三数之和 还是很相似的: 先对数组进行排序, 之后用双指针进行空间优化, 同时注意去重操作. 本质的思想几乎是一样的, 所以对本题不太理解的朋友, 可以先看完上面链接中的 三数之和, 再来看本题题解.
但还是有一些和 三数之和 不同的地方, 主要体现在下面的两个方面:
在 三数之和 中只需要判断相等这一种情况, 其他情况不需要判断, 操作起来是非常简便的, 而本题中每次求和之后都需要进行判断(无论是相等, 还是大于或小于的情况)来找出最接近的数, 这大大增加需要进行判断的工作量, 所以在代码的写法上也有很大的不同之处.
因为 三数之和 没那么多的判断情况, 所以利用了两层for循环来遍历, 去重的操作也比较简单.
for first in range(n): # 需要和上一次枚举的数不相同 if first > 0 and nums[first] == nums[first - 1]: continue ...... # 枚举 b for second in range(first + 1, n): # 需要和上一次枚举的数不相同 if second > first + 1 and nums[second] == nums[second - 1]: continue而本题中判断情况比较多, 不方便使用两重for循环(我也尝试了使用二重循环, 但发现在去重时候非常复杂, 不适合使用此种方法), 所以采用了while语句来进行双指针的遍历, 这样在去重操作上会简便很多, 并且代码中实现的去重方式比官方的要简单, 而且更方便进行记忆!
if s > target: # 如果和大于 target，移动 c 对应的指针 k -= 1 # 移动到下一个不相等的元素 while j < k and nums[k] == nums[k+1]: k -= 1可以计算出每次三数之和的最大最小值和目标值进行比较, 也可以进行优化, 其实这种方法早在之前讲解的 四数之和 中就已经提到了, 但每次都计算也增加了时间消耗, 在 四数之和 中还有很有优化的必要的, 但是在 三数之和 中是否也适用就要看具体的情况了!
class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: nums.sort() n = len(nums) best = 10**7 # 枚举 a for i in range(n): # 保证和上一次枚举的元素不相等 if i > 0 and nums[i] == nums[i - 1]: continue # 使用双指针枚举 b 和 c j, k = i + 1, n - 1 while j < k: s = nums[i] + nums[j] + nums[k] # 如果和为 target 直接返回答案 if s == target: return target # 根据差值的绝对值来更新答案 if abs(s - target) < abs(best - target): best = s if s > target: # 如果和大于 target，移动 c 对应的指针 k -= 1 # 移动到下一个不相等的元素 while j < k and nums[k] == nums[k+1]: k -= 1 else: # 如果和小于 target，移动 b 对应的指针 j += 1 # 移动到下一个不相等的元素 while j < k and nums[j] == nums[j-1]: j += 1 return bestclass Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length; int best = 10000000; // 枚举 a for (int i = 0; i < n; ++i) { // 保证和上一次枚举的元素不相等 if (i > 0 && nums[i] == nums[i - 1]) { continue; } // 使用双指针枚举 b 和 c int j = i + 1, k = n - 1; while (j < k) { int sum = nums[i] + nums[j] + nums[k]; // 如果和为 target 直接返回答案 if (sum == target) { return target; } // 根据差值的绝对值来更新答案 if (Math.abs(sum - target) < Math.abs(best - target)) { best = sum; } if (sum > target) { // 如果和大于 target，移动 c 对应的指针 --k; // 移动到下一个不相等的元素 while (j < k && nums[k] == nums[k+1]) { --k; } } else { // 如果和小于 target，移动 b 对应的指针 ++j; // 移动到下一个不相等的元素 while (j < k && nums[j] == nums[j-1]) { ++j; } } } } return best; }}我的更多精彩文章链接, 欢迎查看
各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)
力扣算法刷题 根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)
计算机专业知识 思维导图整理
最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)
最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目
最值得收藏的 计算机网络 全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介
最值得收藏的 算法分析与设计 全部知识点思维导图整理(北大慕课课程)
最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理
最值得收藏的 人工智能导论 全部知识点思维导图整理(王万良慕课课程)
最值得收藏的 数值分析 全部知识点思维导图整理(东北大学慕课课程)
最值得收藏的 数字图像处理 全部知识点思维导图整理(武汉大学慕课课程)
红黑树 一张导图解决红黑树全部插入和删除问题 包含详细操作原理 情况对比
各种常见排序算法的时间/空间复杂度 是否稳定 算法选取的情况 改进 思维导图整理
人工智能课件 算法分析课件 Python课件 数值分析课件 机器学习课件 图像处理课件
考研相关科目 知识点 思维导图整理
考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)
东南大学 软件工程 906 数据结构 C++ 历年真题 思维导图整理
最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理
最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理
考研思修 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研近代史 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研马原 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研数学课程笔记 考研英语课程笔记 考研英语单词词根词缀记忆 考研政治课程笔记
Python相关技术 知识点 思维导图整理
Numpy常见用法全部OneNote笔记 全部笔记思维导图整理
Pandas常见用法全部OneNote笔记 全部笔记思维导图整理
Matplotlib常见用法全部OneNote笔记 全部笔记思维导图整理
PyTorch常见用法全部OneNote笔记 全部笔记思维导图整理
Scikit-Learn常见用法全部OneNote笔记 全部笔记思维导图整理
Java相关技术/ssm框架全部笔记
科技相关 小米手机
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123204.html
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
摘要：最接近的三数之和给定一个包括个整数的数组和一个目标值。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组，，，和与最接近的三个数的和为答案参考和三数之和一样，我先用的循环，现在用的循环 LeetCode16.最接近的三数之和 JavaScript 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target...
摘要：空间复杂度双指针，循环数组，较小的那个先向内移动如果高的指针先移动，那肯定不如当前的面积大计算面积更新最大面积相交链表方法哈希表思路将链表存入中，第一个相同的节点就是重合的节点复杂度时间复杂度，分别是两个链表的长度。 大厂算法面试之leetcode精讲7.双指针视频教程（高效学习）:点击学习目录：1.开篇介绍2...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
阅读 3606·2021-11-15 11:37
阅读 2974·2021-11-12 10:36
阅读 4400·2021-09-22 15:51
阅读 2379·2021-08-27 16:18
阅读 880·2019-08-30 15:44
阅读 2161·2019-08-30 10:58
阅读 1766·2019-08-29 17:18
阅读 3267·2019-08-28 18:25
