怪兽网站模板,网站备案实名认证,win7系统优化工具,seo课程培训课程三数之和 给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重复的三元组。…三数之和 给你一个整数数组 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 分析
已知:
1、三元组求和: nums[i] nums[j] nums[k] 0
2、要求 i ! j、i ! k 且 j ! k
3、将多余重复的数据 去重 处理 求解算法 双指针
1、初始化两个参数即最左指针left,最右指针right
2、对原数组进行排序处理
3、去重处理三种nums[i] nums[i - 1] 跳过、nums[left] nums[left 1] left 去重、nums[right] nums[right - 1] right-- 去重
题解
// 采用 双指针解决public ListListInteger threeSum(int[] nums) {// 定义一个结果集ListListInteger res new ArrayList();// 对原数组排序Arrays.sort(nums);for (int i 0; i nums.length; i) {// 定义双指针int left i 1;int right nums.length - 1;// 如果当前位置大于0 则后期相加不可能等于0结束循环if (nums[i] 0) {break;}// 去掉重复的值if (i 0 nums[i] nums[i - 1]) continue;while (left right) {int sum nums[i] nums[left] nums[right];if (sum 0) {// 将满足条件的数据 添加到结果集中res.add(Arrays.asList(nums[i], nums[left], nums[right]));// 二次去重 当sum 0时nums[left] nums[left 1],nums[right] nums[right - 1]都会导致数据重复因此需要跳过while (left right nums[left] nums[left 1]) {left;}while (left right nums[right] nums[right - 1]) {right--;}left;right--;} else if (sum 0) {left;} else {right--;}}}return res;}
