本文主要是介绍力扣最热一百题——6.三数之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
题目链接:15. 三数之和 - 力扣(LeetCode)
题目描述
示例
提示
解法一:双指针
代码分析
总结
没啥多说的,就是最近CS根本上不了分谢谢。
题目链接:15. 三数之和 - 力扣(LeetCode)
注:下述题目描述和示例均来自力扣
题目描述
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例
示例 1:
输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] 解释: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1] 输出:[] 解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0] 输出:[[0,0,0]] 解释:唯一可能的三元组和为 0 。
提示
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
解法一:双指针
-
排序:
- 首先,将数组
nums
进行排序。这是因为排序可以简化处理逻辑,使得我们可以使用双指针技术来高效地找到三数之和为零的组合。
- 首先,将数组
-
遍历和去重:
- 使用一个
for
循环遍历数组nums
。对于每个元素nums[i]
,我们尝试找到另外两个元素nums[left]
和nums[right]
,使得它们的和与nums[i]
的和为零。 - 在遍历时,首先检查当前元素
nums[i]
是否大于零。如果nums[i]
大于零,则直接返回结果,因为后面的所有元素也都大于零,不可能再找到和为零的三元组。 - 为了避免重复的三元组,使用一个去重机制。如果当前元素与前一个元素相同,跳过当前元素。
- 使用一个
-
双指针查找:
- 初始化两个指针
left
和right
,分别指向i
之后的第一个元素和数组的最后一个元素。 - 进入
while
循环,通过移动left
和right
指针来寻找满足条件的三元组。- 如果
nums[i] + nums[left] + nums[right]
大于零,则right
向左移动以减少总和。 - 如果小于零,则
left
向右移动以增加总和。 - 如果等于零,则找到了一个满足条件的三元组,将其加入结果列表中。
- 如果
- 初始化两个指针
-
处理重复元素:
- 在找到一个有效三元组后,为了避免结果中出现重复的三元组,需要对
left
和right
指针所指向的元素进行去重处理。 - 移动
left
指针,跳过所有与下一个元素相同的值。 - 移动
right
指针,跳过所有与上一个元素相同的值。
- 在找到一个有效三元组后,为了避免结果中出现重复的三元组,需要对
-
返回结果:
- 最终返回存储所有三元组的
result
列表。
- 最终返回存储所有三元组的
代码分析
-
时间复杂度:
O(n^2)
。排序的时间复杂度是O(n log n)
,而双指针查找的时间复杂度是O(n^2)
,因为每次内层while
循环最多遍历整个数组。 -
空间复杂度:
O(1)
(不包括返回结果空间)。算法只使用了固定数量的额外空间来存储指针和变量。
class Solution {public List<List<Integer>> threeSum(int[] nums) {//创建需要返回的集合ArrayList<List<Integer>> result = new ArrayList<>();//将数组nums进行排序Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {//排序之后如果第一个数已经大于0,则已经不可能使和为0if (nums[i] > 0){return result;}//防止重复元素加入,现在进行去重操作if (i > 0 && nums[i] == nums[i - 1]){//发现为重复元素,跳过这次循环continue;}//定义left和right两个指针int left = i + 1;int right = nums.length - 1;//开始查找合适的集合元素while ( left < right){if (nums[i] + nums[left] + nums[right] > 0){//大于0,right左移\right--;}else if (nums[i] + nums[left] + nums[right] < 0){//小于0,left右移\left++;}else {//获得正确目标,将目标加入result集合result.add(Arrays.asList(nums[i] , nums[left] , nums[right] ));//同时在加入之后防止找到重复的目标,进行while中的去重操作while (left < right && nums[left] == nums[left + 1]){//left重复,将left右移left++;}while (left < right && nums[right] == nums[right - 1]){//right重复,将right左移right--;}//去重操作完毕,将继续while遍历,寻找目标值,移动left和rightleft++;right--;}}}return result;}
}
总结
多多熟悉就好啦!!!今天也开学了,我也刚发布了一篇图像识别的文章,大家多多支持谢谢!!!!!
链接如下:实时图形识别的实现:模板匹配与几何特征方法的对比-CSDN博客
感谢大家的支持!!!
这篇关于力扣最热一百题——6.三数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!