[数据结构与算法]leetcode-day18:3Sum(三数之和)

15. 3Sum

哈希表：解决了两数之和，那么能解决三数之和么？

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$

逻辑分析：

保证数组有序：
遍历数组时，遍历到的值nums[i]为第一个数，num[left],num[right]组成双指针，分别为第二个数和第三个数。
left=i+1;
right=nums.length-1;
然后做判断：
和大于0则right--,和小于0则left++,等于0则放入结果数组，继续向后寻找。

JAVA代码实现：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        
        for(int i=0;i<nums.length;i++){
            //数组已经有序,避免做无意义的判断
            if(nums[i]>0){
                return result;
            }
            
            //避免重复
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            
            int left = i+1;
            int right=nums.length-1;
            
            while(left<right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }
                if(sum<0){
                    left++;
                }
                
                if(sum==0){
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while(left<right && nums[right]==nums[right-1]){
                        right--;
                    }
                    while(left<right && nums[left]==nums[left+1]){
                        left++;
                    }
                    //继续寻找nums[i]作为第一个数，与其余的两个数之和为0。
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}