建设商务网站,建筑工程公司起个名字,做手机网站,wordpress自定义简单注册题目描述#xff1a;给你一个包含 n 个整数的数组 nums#xff0c;判断 nums 中是否存在三个元素 a#xff0c;b#xff0c;c #xff0c;使得 a b c 0 请你找出所有和为 0 且不重复的三元组。 注意#xff1a;答案中不可以包含重复的三元组。
输入#xff1a;nums …题目描述给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 请你找出所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。
输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]]
输入nums [] 输出[]
输入nums [0] 输出[]
第一步可以对已有的数组作一个排序保证数组升序排序由左至右逐渐增大。为了后续操作做准备。 第二步创建左右两个指针循环数组将i的位置的值当作是我们自己左右指针分别指向两个队友两个数。 第三步每一次都做验证三个值相加看一下三个值相加的结果到底是大了还是小了。 第四步移动指针由于目前数组已经有序了如果值大于0 则大的数小一些即可右指针左移反之小于0左指针右移 public ListListInteger threeSum2(int[] nums) {int n nums.length;ListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i n; i) {if (nums[i] 0) break;if (i 0 nums[i] nums[i - 1]) continue; int leftPoint i 1; int rightPoint n - 1; // 右指针为n-1 就是循环完全部数组while (leftPoint rightPoint) {int num nums[i] nums[leftPoint] nums[rightPoint];if (num 0) {result.add(Arrays.asList(nums[i], nums[leftPoint], nums[rightPoint])); leftPoint;rightPoint--; while (leftPoint rightPoint nums[leftPoint] nums[leftPoint - 1]) leftPoint;while (leftPoint rightPoint nums[rightPoint] nums[rightPoint 1]) rightPoint--;} else if (num 0)leftPoint;elserightPoint--;}}return result;
}复杂度分析 我们程序中使用了一个for循环加若干个while但是我们会发现while循环的整体次数 其实就是n的次数所以时间复杂度应该是O(N)。 空间复杂度只使用了几个固定的值如n,左指针,右指针等 所以空间复杂度是O(1)
