娄底市住房和城乡建设局网站,wordpress 自定义链接地址,WordPress情侣网站,一个人做电商网站难吗15. 三数之和
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重复的三元…15. 三数之和
给你一个整数数组 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 题解
法一排序 双指针
1. 先将目标数组排序使其由小到大排序
Arrays.sort(nums);
2. 基本逻辑设置三个指针第一个指针i从头开始遍历第二个指针left在i后一个位置开始遍历第三个指针right则从最后一个位置开始遍历。
for(int i 0;i nums.length;i) {int left i 1;int right nums.length - 1;while(right left) {int sum nums[i] nums[left] nums[right];if(sum 0) {right--;}else if(sum 0) {left;}else {res.add(Arrays.asList(nums[i],nums[left],nums[right]));right--;left;}}}
3. 特殊情况直接返回
若nums[0]指向0则证明所有元素都大于0不可能会有三个数之和大于0返回空列表。
if(nums[0] 0) {return res;}
4. 去重操作
4.1 对i指针去重
i指针指向的新元素与其之前指向的元素为同一个元素直接跳过
if(i 0 nums[i] nums[i - 1]) {continue;}
4.2 对left、right指针去重(添加新结果是进行去重)
while(right left nums[right] nums[right - 1]){right--;}
while(right left nums[left] nums[left 1]) {left;}
整体代码实现
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger res new ArrayList();Arrays.sort(nums);for(int i 0;i nums.length;i) {if(nums[0] 0) {return res;}if(i 0 nums[i] nums[i - 1]) {continue;}int left i 1;int right nums.length - 1;while(right left) {int sum nums[i] nums[left] nums[right];if(sum 0) {right--;}else if(sum 0) {left;}else {res.add(Arrays.asList(nums[i],nums[left],nums[right]));while(right left nums[right] nums[right - 1]){right--;}while(right left nums[left] nums[left 1]) {left;}right--;left;}}}return res;}
}
