深圳 网站托管,安阳河南网站建设,wordpress运行php代码,网站地图怎么做XML文章目录 题目解题思路代码 题目
给你一个整数数组 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 。
提示
3 nums.length 3000 -105 nums[i] 105
解题思路 因为只需要知道对应的数组值不需要知道下标所以考虑用双指针方法先把原数组排序然后双指针来算出三数之和与零比较具体可以看代码中的注释 代码
class Solution {//采用双指针的方法因为这回要求返回的是数组中的值不需要返回数组下标所以可以用双指针的方式来返回值public ListListInteger threeSum(int[] nums) {//定义返回集合ListListInteger resultnew ArrayList();int left0;int right0;//先把数组进行排序Arrays.sort(nums);for (int i 0; i nums.length; i) {//nums[i]作为相加的第一个元素if(nums[i]0){//排序完之后,nums是从小到大排序如果第一个元素就已经大于0了就跳出循环就行了break;}if (i0nums[i]nums[i-1]){//这个地方的意义是去重题目中要求答案不可以包含重复的三元组)// 假如nums是[-1,-1,-1,1,,1,2,3,4],前三个元素没必要每次循环都试一遍直接找到nums[2]对应的-1开始就可以了continue;}lefti1;right nums.length-1;while (leftright){//如果三个数之和大于零就right--,if((nums[i]nums[left]nums[right])0){right--;}else if((nums[i]nums[left]nums[right])0){//如果三个数之和小于零就leftleft;}else{//如果是相等就把结果加入到返回集合当中ListInteger list new ArrayList();list.add(nums[i]);list.add(nums[left]);list.add(nums[right]);result.add(list);//把后两位数也去重避免返回相同的数while (leftrightnums[left]nums[left1]){left;}while (leftrightnums[right]nums[right-1]){right--;}left;right--;}}}return result;}
}
