15. 3Sum

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int target = 0 - nums[i];
            int lo = i + 1, hi = n - 1;
            
            while (lo < hi) {
                int tmpSum = nums[lo] + nums[hi];
                if (tmpSum == target) {
                    res.add(Arrays.asList(new Integer[]{nums[i], nums[lo], nums[hi]}));
                    lo++;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                    hi--;
                    while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
                } else if (tmpSum < target) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }
        
        return res;
    }
}