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;
    }
}