题目:
分析:由题意,很容易看出可以三层循环,但是时间复杂度就为O(n^3)很容易运行超时,想办法进行简化
(1)排序 要求三数相加为0 ,要是排序之后的数据都为正数,则必然不满足条件 直接break
(2)三者关系 相加为0 则a+b+c=0 即c = -(a + b)则有可能不用循环c 而是通过a和b计算出来
(3)题不存着重复数据,则在循环时,可进行判断前后数据是否一样,一样则不用再次进行操作
代码:
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); int len = nums.length; if(len < 3){ //长度不够3 直接返回 return result; } Arrays.sort(nums); //排序 for(int i = 0;i < len;i ++){ if(nums[i] > 0) { //当前数大于0 后面的必全大于0 无法相加为0 break; } Integer first = nums[i]; //得到第一位置的数 if(i > 0 && nums[i] == nums[i - 1]){ //两个数相同,则直接继续下一次循环 continue; } Set<Integer> set = new HashSet<>(); //用于储存第二位置的数 for(int j = i + 1; j < len;j ++){ Integer third = nums[j]; //第三位置的数 Integer second = -(first + third); //计算第二位置的数 if(set.contains(second)){ //在set中找是否有数与计算出的第二位置的数相等 result.add(new ArrayList<>(Arrays.asList(first,second,third))); //加入 while(j < len - 1 && nums[j] == nums[j + 1]) //同样存在相同的数 继续下一次循环 存着j + 1 则 j < len - 1,否则数组越界 j++; } set.add(third); //不管满足不满足,先放进去 } } return result; } }
时间复杂度则为O(n^2)
标签:set,third,nums,--,三数,50,len,int,result From: https://www.cnblogs.com/tianhuida/p/16729858.html