lc-15

//Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k
//]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. 
//
// Notice that the solution set must not contain duplicate triplets. 
//
// 
// Example 1: 
// Input: nums = [-1,0,1,2,-1,-4]
//Output: [[-1,-1,2],[-1,0,1]]
// Example 2: 
// Input: nums = []
//Output: []
// Example 3: 
// Input: nums = [0]
//Output: []
// 
// 
// Constraints: 
//
// 
// 0 <= nums.length <= 3000 
// -105 <= nums[i] <= 105 
// 
// Related Topics Array Two Pointers Sorting 
// 👍 18445 👎 1774


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        if (nums == null || nums.length <= 2) {
            return result;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int start = j + 1;
                int end = nums.length - 1;
                int target = -(nums[i] + nums[j]);

                if (target < 0) {
                    break;
                }
                while (start <= end) {
                    if (start + 1 >= end) {
                        if (nums[start] == target) {
                            List<Integer> oneR = new ArrayList<>();
                            oneR.add(nums[i]);
                            oneR.add(nums[j]);
                            oneR.add(nums[start]);
                            result.add(oneR);
                        } else if (nums[end] == target) {
                            List<Integer> oneR = new ArrayList<>();
                            oneR.add(nums[i]);
                            oneR.add(nums[j]);
                            oneR.add(nums[end]);
                            result.add(oneR);
                        }
                        break;
                    }

                    int mid = start + (end - start) / 2;
                    if (nums[mid] == target) {
                        List<Integer> oneR = new ArrayList<>();
                        oneR.add(nums[i]);
                        oneR.add(nums[j]);
                        oneR.add(nums[mid]);
                        result.add(oneR);
                        break;
                    } else if (nums[mid] < target) {
                        start = mid;
                    } else {
                        end = mid;
                    }
                }
            }
        }

        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)