很有意思的一道题,值得好好思考,虽然难度只有Mid,但是个人觉得不比Hard简单
题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = []
输出:[]
示例 3:
输入:nums = [0]
输出:[]
提示:
- 0 <= nums.length <= 3000
- -105 <= nums[i] <= 105
解答
解法一 排序+双指针+三循环
很容易想到的是先对序列进行排序,首尾两个指针,两个指针中间采取遍历,三个循环查找所有满足条件的答案。
时间复杂度为\(O(n^3)\) 空间复杂度为 \(O(n)\)
然后一开始就疯狂说超时,结果一番修改,终于不报超时了。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int len = nums.length;
// 对数组进行排序
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 定义一个指针,指向数组的头部,不断的去遍历每一个不重复的元素
// 每次遍历中再定义一个指针指向尾部,不断往前遍历,判断是否存在合理的三元组
for (int pi = 0; pi < len - 2; pi++) {
// 很明显如果pi对应的值都大于0了,说明后面的全是大于0,已无解了
if (nums[pi] > 0) {break;}
for (int pj = len - 1; pj > pi; pj--){
// 这里的pj值小于0,也是一样的,代表这一轮已无解了直接break
if (nums[pj] < 0) {break;}
for (int pz = pj - 1; pz > pi; pz--) {
if (nums[pi] + nums[pj] + nums[pz] > 0) { continue; }
if (nums[pi] + nums[pj] + nums[pz] < 0) { break; }
if (nums[pi] + nums[pj] + nums[pz] == 0){
List<Integer> temp = new ArrayList<Integer>();
temp.add(nums[pi]);
temp.add(nums[pz]);
temp.add(nums[pj]);
ans.add(temp);
// 找到就退出此循环
break;
}
// 走到最后一个相同元素的位置
while (pz > 0 && nums[pz] == nums[pz - 1]) {pz--;}
}
// 走到最后一个相同元素的位置
while (pj > 0 && nums[pj] == nums[pj - 1]) {pj--;}
}
// 走到最后一个相同元素的位置
while (pi < len - 1 && nums[pi] == nums[pi + 1]) {pi++;}
}
return ans;
}
}
// 执行用时: 2164 ms
// 内存消耗: 42.3 MB
不报超时了,但是时间大概就比别人多了很多很多吧
果然时间复杂度太高了,但是想了半天也不知道是为什么,然后去看教程,教程说能将三循环优化成双循环。
一看代码还是三循环,人傻了反正是。
虽然没懂为什么for改成while起作用了,但是直接动手改写我最后的一层循环。
写着写着就悟了。。。果然实践出真知
直接上代码吧
解法二 排序+双指针+双循环
时间复杂度\(O(n^2)\)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int len = nums.length;
// 对数组进行排序
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 定义一个指针,指向数组的头部,不断的去遍历每一个不重复的元素
// 每次遍历中再定义一个指针指向尾部,不断往前遍历,判断是否存在合理的三元组
for (int pi = 0; pi < len - 2; pi++) {
// pi指向的元素如果大于0,后面无解,直接返回
if (nums[pi] > 0) {return ans;}
int pz = pi + 1;
for (int pj = len - 1; pj > pi; pj--){
// pj指向的元素如果都小于0,说明剩余区域全部为零了,直接break
// pz指向大于pj时说明无解了
if (nums[pj] < 0 || pz >= pj) {break;}
// 更新pz
while (pz < pj && nums[pi] + nums[pj] + nums[pz] < 0) {
pz++;
}
// 记录pz如果合理
if (pz < pj && nums[pi] + nums[pj] + nums[pz] == 0){
List<Integer> temp = new ArrayList<Integer>();
temp.add(nums[pi]);
temp.add(nums[pz]);
temp.add(nums[pj]);
ans.add(temp);
}
// 走到最后一个相同元素的位置
while (pj > 0 && nums[pj] == nums[pj - 1]) {pj--;}
}
// 走到最后一个相同元素的位置
while (pi < len - 1 && nums[pi] == nums[pi + 1]) {pi++;}
}
return ans;
}
}
// 执行用时: 24 ms
// 内存消耗: 42.8 MB
这速度反正快了很多很多吧
why?
首先说明,数组按照从小到大的顺序排序,
我们最外层的循环是遍历指向数组头的指针,Head
第二层的循环是遍历指向数组尾的指针,Tail
第三层的循环是两个首尾指针中间的区域,Mid
对于一个Head,我们的尾指针Tail 将会从最后一个元素慢慢往前遍历至头元素的前一个元素。
假如此时 Head = \(n\), Tail = \(m\),\(n<m\),如果找到一个Mid =\(x\), \(n<x<m\)
满足条件 \(nums[n] + nums[x] +nums[m] = 0\)
那么此时Tail更新为\(m-1\),那么我们第三层循环的Mid指针需要重新从\(n+1\)开始遍历吗?
答案是不需要。
为什么?
此时有 \(nums[n] + nums[x] +nums[m] = 0, nums[m-1]<nums[m]\)
所以不难推出 \(nums[n]+nums[x]+nums[m-1]<0\)
因此\(x\)左边的值都只会使不等式小于0,我们只需要从\(x\)往右开始遍历Mid就可以了。
说到这里,可以发现Mid指针,在Head指针固定的情况下,只会更新小于len次,len为数组的长度。
也就是说当Head=\(n\)时,
Mid指针只会遍历小于\(length(nums)-n\)次,
而Tail指针,也是遍历小于\(length(nums)-n\)次
分配下来,Tail的一次循环Mid更新的次数是常数项。而在某些时刻Mid会直接大于Tail,就直接退出内层循环。
因此第三层循环虽然是存在,但是在第二层循环的指针固定的情况下,只会循环常数项次,至此第三层循环由\(O(n)\)被优化至\(O(1)\)