宁波建设系统网站,湘潭房产网站建设,南京网站排名公司,教育机构跑路给你一个整数数组 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) {Arrays.sort(nums);ListListInteger results new ArrayListListInteger();ListInteger result new ArrayListInteger();HashMapListInteger, ListInteger map new HashMap();
// int n 1;// 三重循环超时for (int i 0; i nums.length; i){for (int j i1; j nums.length; j){for (int k j1; k nums.length; k){if (nums[i] nums[j] nums[k] 0){result.add(nums[i]);result.add(nums[j]);result.add(nums[k]);// System.out.println(result);// 判断是否重复if (!map.containsValue(result)){map.put(result, result);
// n;results.add(result);}// System.out.println(results);result new ArrayListInteger();// System.out.println(result);}}}}return results; }
}最终代码
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger ans new ArrayList();if (nums null || nums.length 2) return ans;Arrays.sort(nums); //从小到大排序Onlognfor (int i0; i nums.length - 2; i){if (nums[i] 0) break; //第一个数大于0后面的数都比它大肯定不成立if (i 0 nums[i] nums [i-1]) continue; //去掉重复的情况int target -nums[i];int left i 1;int right nums.length - 1;while (left right){if (nums[left] nums[right] target){ans.add(new ArrayList(Arrays.asList(nums[i], nums[left], nums[right])));// 现在要增加 left减小 right但是不能重复比如: [-2, -1, -1, -1, 3, 3, 3], i 0, left 1, right 6, [-2, -1, 3] 的答案加入后需要排除重复的 -1 和 3//增加left和减少right left; right--;//去重while(left right nums[left] nums[left - 1]) left;while(left right nums[right] nums[right 1]) right--;}else if(nums[left] nums[right] target){//两个数相加小于target左指针向右移left;}else if(nums[left] nums[right] target){//两个数相加大于target右指针向左移right--;}}}return ans;}
}
