原始问题陈述:
给定一个整数数组nums,返回所有三元组[nums[i],nums[j],nums[k]],使得i!= j,i!= k,j!= k,并且nums[i] + nums[j] + nums[k] == 0。
请注意,解决方案集不得包含重复的三元组。
我的解决方案:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
ArrayList<Integer> temp;
int left, right, sum;
for(int i = 0; i < nums.length; i++){
left = i+1;
right = nums.length - 1;
while(left < right){
sum = nums[i] + nums[left] + nums[right];
if(sum == 0){
temp = new ArrayList<Integer>();
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
if(ans.contains(temp) == false){
ans.add(temp);
left++;
continue;
}
left++;
continue;
}else if(sum<0){
left++;
continue;
}else{
right--;
continue;
}
}
}
return ans;
}
}
我在LeetCode的测试用例311/312中得到了TLE,这是一个非常大的数组,值也很大。我一直在寻找一种方法来优化它,但似乎想不出答案。我真的很感激任何关于该怎么做的提示。谢谢。
1条答案
按热度按时间cyej8jka1#
有一个问题(bug),在找到具有相同值的其他List示例时,
List.contains
将不为true。存储Set<Integer>
将有效。但是,重复的值将从集合中删除。你的代码可以写成:
声明可以接近用法,对变量的内存使用没有影响。Continues也是一个风向标。
对于优化来说,第一件事是数据结构。拥有一个3个整数的列表不如一个
int[3]
数组好。你也可以使用这些值,并在整个循环中将它们保存在变量中。另一个优化是有两个值,可以确定第三个查找的值。在排序数组中,* 二分搜索 * 将产生该索引(或
-index-1
,当没有找到插入位置时)。与在循环中向解决方案移动索引相比,这种二分搜索将大大加快算法的速度。然后是对超出界限的候选人的捷径循环。也许没有实现100%,但足够。
Contains check和adding best是一起做的,如果答案真的很多,比如有一千个0,那也需要考虑一下,
Set
可能是个好主意。