题目来源于力扣题库,题目链接:LC15. 三数之和
Q:给你一个整数数组 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
-105 <= nums[i] <= 105
A:思路:题目给出的要求是从一个整数数组中不断找到三数之和为0的三元组,条件是这三个数所对应的索引均不相同,且结果集中不能存在重复的三元组。
拿到该题,最容易想到的是用暴力解法,三个for循环开干。但是,通过对时间复杂度的一个分析,发现这样是行不通的,随后,曾经做过的两数之和的思路可能突然间给了自己一个思路,即用哈希表来做。事实上,利用哈希表是可以做出来的,但是过程有些过于复杂,尤其是对于去重问题,且时间复杂度也不低。
最后,只能去求助于双指针,双指针的主要思路是先对数组进行排序,然后利用一层for循环去的固定一个数值nums[i](i∈[0, nums.length - 1]),随后构建两个指针left和right,初始化使得left = i + 1,right = nums.length - 1(left指向i的下一个数值,right指向nums的最后一个数值),在while(left < right)循环中,去使得left和right不断的靠近,即left++,right--。由于数组是经过排序的,所以是递增的,当遇到nums[i] + nums[left] + nums[right] > 0时,说明和太大了,那么我们就让right指针往前移动right--,使得和变小一点;同理如果遇到nums[i] + nums[left] + nums[right] < 0时,那么说明总和太小了,我们就让left指针往后移动left++,使得和变大一点。这样不断的去找到满足nums[i] + nums[left] + nums[right] == 0 的三个数值,且它们的下标是不重复的,但是还有一个问题就是,如何解决结果集中重复的三元组组合问题呢?
这里便涉及到了关键的操作:去重,如何去重,举例来讲,例如有一数组: {-1, -1, -1, 2},我们可以发现,里面的一个组合{-1, -1, 2}是满足题意的,但是如果不进行去重操作,那么就会出现重复的三元组{-1, -1, 2}。解决该问题的一个关键思路是如果当前for循环中需要固定的数值num[i] == nums[i-1]时,就直接continue,跳过此轮for循环。为什么要这样?因为nums[i - 1]已经被我们用过了,且其后面对应的一些可以满足组合的数值也都用过了,均加入了结果集中了。那么如果现在我们还使用与nums[i-1]相同数值的nums[i],并且同样的往后找到满足的组合,那么必定会出现重复的三元组,简单来说就是又以同样的数值nums[i]去找了一遍满足题意的组合。
故我们得知去重的第一个条件就是在for循环中,如果遇到i > 0 && nums[i] == nums[i - 1],则直接continue,开启下一轮for循环。但是现在似乎只完成了一次去重,还有二次去重,例如nums:{0, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1},我们可以很容易的找到满足题意的三元组{0,-1,1},但是此时会出现往后的{0,-1,1}还是满足的,显然这是不符合题意的,虽然它们三个下标不同,但是三元组是重复的。其实这个问题其实很好解决,当我们发现nums[left] == nums[left + 1] 时,就让left指针不断的往后移动,即left++,跳过那些重复的数值;同理当我们发现nums[right] == nums[right - 1]时,就让right指针不断的往前移动,即right--即可,至此,二次去重问题便解决了。
最后要说的是,每当找到一组满足题意的三元组加入到结果集后,且二次去重完成后,还要进行一次left++和right--,使得left和right指针指向下一个需要判断的三元组。
以下是Java代码,仅供参考:
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); // 排序 for(int i = 0; i < n; i++){ if(nums[i] > 0) return res; // 排序后的第一个数值如果已经大于0,则直接返回res if(i > 0 && nums[i] == nums[i - 1]) continue; // 一次去重 int left = i + 1; // 对于每一次的i,更新left int right = n - 1; // 对于每一次的i,更新right while(left < right){ int sum = nums[i] + nums[left] + nums[right]; if(sum < 0){ // 总和太小了,使left往后挪一挪 ++left; }else if(sum > 0){ // 总和太大了,使right往前挪一挪 --right; }else{ res.add(Arrays.asList(nums[i], nums[left], nums[right])); // 收集结果 while(left < right && nums[left] == nums[left + 1]) ++left; // 二次去重 while(left < right && nums[right] == nums[right - 1]) --right; // 二次去重 ++left; // 指向下一个待判断的数值 --right; // 指向下一个待判断的数值 } } } return res; } }
标签:right,nums,++,三数,数值,三元组,LC15,left From: https://www.cnblogs.com/fxy0715/p/17418493.html