15 3Sum

Leetcode

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 -10^5 <= nums[i] <= 10^5

---

先将数组排序。一次遍历数组，选为第一个数。两个指针从两侧向内判断剩下的数是否满足条件，如果和过大，右边的指针向左移动，和过小，左边的指针向右移动。移动的过程中如果遇到重复的，继续移动，以去重。时间复杂度 O(n²)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new LinkedList<>();
        if(nums==null || nums.length<3) return res;
        Arrays.sort(nums);
        int j,k,t;
        for(int i=0;i<nums.length-2;++i){
            if(i>0 && nums[i]==nums[i-1]) continue;
            if(nums[i]>0) break;
            j=i+1; k=nums.length-1;
            while(j<k){
                t=nums[i]+nums[j]+nums[k];
                if(t>0)
                    --k;
                else if(t<0)
                    ++j;
                else{
                    List<Integer> list=new LinkedList<>();
                    list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);
                    res.add(list);
                    ++j;--k;
                    while(j<k && nums[j]==nums[j-1]) ++j;
                    while(j<k && nums[k]==nums[k+1]) --k;
                }
            }
        }
        return res;
    }
}
~~