题目:https://leetcode-cn.com/problems/3sum/submissions/
代码:
class Solution { public List<List<Integer>> threeSum(int[] nums) { int length = nums.length; Arrays.sort(nums); List<List<Integer>> res = new ArrayList<List<Integer>>(); int sum; for (int i = 0; i < length - 2; i++) { if (nums[i] > 0) { break; } if (i>0 && nums[i]==nums[i-1]){ continue; } int l = i+1; int r = length-1; while(l<r){ sum = nums[i]+nums[l]+nums[r]; if (sum == 0) { res.add(Arrays.asList(nums[i],nums[l],nums[r])); while (l<r && nums[l] == nums[l + 1]) { l++; } while (l<r && nums[r] == nums[r - 1]) { r--; } l++; r--; } else if (sum < 0) { l++; } else if (sum > 0){ r--; } } } return res; } }
思路:
1、先将数组按照从小到大进行排序,然后遍历数组。用i做索引
2、对nums[i]进行判断,如果大于0则退出循环。原因:数组是从小到大排列的,如果第一个数都大于0,那么后面的数是大于第一个数的,所以无论如何sum值都不会为0。
3、在遍历nums[i]的时候,设置双指针,一个l一个r,分别从i后面的剩余元素一个左边一个右边进行遍历。在sum值小于0的时候,证明l索引所在的值太小了,需要变大一点即l++;在sum值大于0的时候,证明r索引所在的值太大了,需要变小一点,即r--。
4、经过以上3个条件已经可以得出结果了,但是在某些情况下结果会重复,所以需要进行去重优化,即代码中的第一层for循环中的if语句以及sum=0时的2个while语句。作用都一样。就是判断当前元素是否更上一个元素一样。一样的话得出的结果肯定是重复值,则可以直接跳过。
注意:
1、在去重这里花费的时间比较多。可以好好考虑一下。
2、在找到sum=0的时候,需要将3个元素添加到一个list中,然后再添加到res中,这里可以直接用Arrays.asList()方法做处理。省去自己new一个list然后挨个add的麻烦。