力扣算法打卡刷题|??导图整理数组5: 四数之和 相比 三数之和 的大量优化, 力扣18详细注解??
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.目录
目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).
关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接. 欢迎和博主一起打卡刷力扣算法, 博主同步更新了算法视频讲解 和 其他文章/导图讲解, 更易于理解, 欢迎来看!
0.导图整理
1.思想同三数之和: 排序+双指针
2.在三数之和基础上进行了大量的优化
源码
题目链接:https://leetcode-cn.com/problems/4sum/
0.导图整理
文章图片
1.思想同三数之和: 排序+双指针 四数之和 本质上和 三数之和 是一样的, 由于都有大量重复元素的存在, 都不能使用哈希表进行简单的去重, 都需要先进行排序后才方便遍历处理, 同时为了优化时间复杂度, 再加上双指针方法的使用, 如果只是想简单实现的话, 那么在 三数之和 上直接多加一重循环, 修改一下细节, 本题就可以实现了, 但是上述代码的不同点在于: 并非只是简单的加了一重循环而已, 而是进行了大量的优化处理.
2.在三数之和基础上进行了大量的优化 因为 四数之和 相比较于 三数之和 来说, 情况更加复杂, 时间复杂度也更高, 而且这个时间复杂度通过算法是很难降下来的, 我们只能通过对代码进行优化, 直接减少大量不必要的遍历情况, 从而来缩短代码的运行时间.
对于代码的优化主要分为两大块: 一部分是为了避免出现重复的四元组, 在遍历上面的优化, 这部分内容和 三数之和 中是相似的处理, 只不过更加复杂.
首先是对前两重循环进行的去重操作, 当 i 或者 j 的值与前面的值相等时忽略, 之后又对 双指针 进行了去重操作, 这里有个重要的注意点: 一定注意代码中是 先进行了指针的移动还是先进行了去重的比较, 对于不同的顺序, 比较的元素是完全不同的. 如果先进行了指针的移动, 对于左指针来说, 需要比较的元素就是 当前元素和前面的一个元素, 如果是先进行去重的比较, 那比较的元素就是 当前元素和后面的一个元素, 再进行指针的移动. 对于右指针的情况正好是完全相反的.
第二部分就是在循环遍历中先通过计算特定的四个数之和, 以此来判断接下来的循环操作情况.
比如 在确定第一个数 nums[i] 之后, 如果nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target, 也就是此时的最小的4个数之和都大于target, 说明此时剩下的三个数无论取什么值, 四数之和一定大于 target, 因此直接退出第一重循环就可以了, 使用 break 关键字.
在确定第一个数 nums[i] 之后,如果nums[i]+nums[n?3]+nums[n?2]+nums[n?1]
源码Python:
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
quadruplets = list() # 定义一个返回值
if not nums or len(nums) < 4:
return quadrupletsnums.sort()
length = len(nums)
# 定义4个指针i,j,left,righti从0开始遍历,j从i+1开始遍历,留下left和right作为双指针
for i in range(length - 3):
if i > 0 and nums[i] == nums[i - 1]: # 当i的值与前面的值相等时忽略
continue
# 获取当前最小值,如果最小值比目标值大,说明后面越来越大的值根本没戏
if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
break # 这里使用的break,直接退出此次循环,因为后面的数只会更大
# 获取当前最大值,如果最大值比目标值小,说明后面越来越小的值根本没戏,忽略
if nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target:
continue # 这里使用continue,继续下一次循环,因为下一次循环有更大的数
# 第二层循环j,初始值指向i+1
for j in range(i + 1, length - 2):
if j > i + 1 and nums[j] == nums[j - 1]: # 当j的值与前面的值相等时忽略
continue
if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
break
if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target:
continue
left, right = j + 1, length - 1
# 双指针遍历,如果等于目标值,left++并去重,right--并去重,当当前和大于目标值时right--,当当前和小于目标值时left++
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
left += 1 # left先+1之后,和它前面的left-1进行比较,若后+1,则和它后面的left+1进行比较
while left < right and nums[left] == nums[left - 1]:
left += 1
right -= 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif total < target:
left += 1
else:
right -= 1return quadrupletsjava:
class Solution {
public List> fourSum(int[] nums, int target) {
List> quadruplets = new ArrayList>();
// 定义一个返回值
if (nums == null || nums.length < 4) {
return quadruplets;
}
Arrays.sort(nums);
int length = nums.length;
// 定义4个指针i,j,left,righti从0开始遍历,j从i+1开始遍历,留下left和right作为双指针
for (int i = 0;
i < length - 3;
i++) {
if (i > 0 && nums[i] == nums[i - 1]) { // 当i的值与前面的值相等时忽略
continue;
}
// 获取当前最小值,如果最小值比目标值大,说明后面越来越大的值根本没戏
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
// 这里使用的break,直接退出此次循环,因为后面的数只会更大
}
// 获取当前最大值,如果最大值比目标值小,说明后面越来越小的值根本没戏,忽略
if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
// 这里使用continue,继续下一次循环,因为下一次循环有更大的数
}
// 第二层循环j,初始值指向i+1
for (int j = i + 1;
j < length - 2;
j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) { // 当j的值与前面的值相等时忽略
continue;
}
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
int left = j + 1, right = length - 1;
// 双指针遍历,如果等于目标值,left++并去重,right--并去重,当当前和大于目标值时right--,当当前和小于目标值时left++
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
left++;
// left先+1之后,和它前面的left-1进行比较,若后+1,则和它后面的left+1进行比较
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
right--;
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
}
} 【力扣算法打卡刷题|??导图整理数组5: 四数之和 相比 三数之和 的大量优化, 力扣18详细注解??】
感觉作者写的不错的, 别忘了点赞关注加收藏哦(一键三连)!你的支持会带给我极大的动力, 写出更多优秀文章!
我的更多精彩文章链接, 欢迎查看
各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)
力扣算法刷题 根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)
计算机专业知识 思维导图整理
最值得收藏的 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的性能情况和常见后缀的含义 思维导图整理
推荐阅读
- Ⅴ爱阅读，亲子互动——打卡第178天
- 画解算法（1.|画解算法：1. 两数之和）
- 2018-3-24
- 日志打卡
- 以读攻“毒”唤新活动曹彦斌打卡第二天
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 泰拳居家打卡十九天