Problem: 15. 三数之和

• 时间复杂度: $O(n^2)$

🍑 AC code

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();int len = nums.length;  if(len < 3) return res;Arrays.sort(nums);for(int i = 0; i < len; i++){if(nums[i] > 0)break;if(i > 0 && nums[i] == nums[i-1])//去重 第一个选的数continue;int l = i+1;int r = len-1;while(l < r){int sum = nums[i] + nums[l] + nums[r];if(sum == 0){res.add(Arrays.asList(nums[i],nums[l],nums[r]));//去重 l 和 r 的数// 注意：当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;}
}