Leetcode --- 3Sum
===

## Description
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.

### Examples

* Ex1:
**Input**: nums = [-1,0,1,2,-1,-4]
**Output**: [[-1,-1,2],[-1,0,1]]
* Ex2:
**Input**: nums = []
**Output**: []

### Constraints

* 0 <= nums.length <= 3000
* -10^5^ <= nums[i] <= 10^5^

## Solution

Obviously,it is an extension question of the Two Sum question,therefore,we only take each element in the array to be the target,and the negative each element is gonna be the target value because of the below formula,and the question will be done.

nums[cur] + (nums[i] + nums[j] )=0 
                    ^
                    |
                 Two Sum
=>
(nums[i] + nums[j] ) = -nums[cur] = target

But here's thing,Two sum question has a constraint that each element in the array are appeared exactly once,it is a bit different but a big bug in here,the bug is that the HashTable can't be used once again because the HashTable can't accept the identical keys in the table.

So,I wanna use two pointers to point to the first position and the last position in the array,and compare the sum and the target,it will has 3 cases:
* nums[left] + nums[right] > target => right=right-1,because the array have sorted and the sum is too big.
* nums[left] + nums[right] < target => left=left+1
* nums[left] + nums[right] = target => find the answer!

### Implement code

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        if(nums.length <3)
            return new ArrayList<>();
        
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        
        for(int i = 0 ; i < nums.length-2 ; i++ )
        {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int target = -nums[i];
            int left = i+ 1 ;
            int right  = nums.length -1 ;
          
            while(left < right )
            { 
                if((nums[left] + nums[right]) > target)
                    right--;
                else if((nums[left] + nums[right]) < target)
                    left++;
                else
                {
                    List<Integer> list = Arrays.asList(nums[i],nums[left++],nums[right--]);
                    ans.add(list);
                    while(left < right && nums[left] == nums[left-1])left++;
                    while(left < right && nums[right] == nums[right+1] )right--;
                }   
            }
        }
        return ans;
    }
}  

### Complexity Analysis

* Time Complexity
First for loop from line 10 to line 33 must go through n-2 iterations,which n is length of input array,in term Big O notation is O(n).
Second while loop from line 17 to line 30 may take n-1 times when left++ until left is greater than right in worse case => O(n)
Third and fourth while loop at line 27 and line 28 is an accelerating loop for the external while loop so we can ignore their costs.
.
Overall time complexity:
O(n) * O(n) = **O(n^2^)**
==Key Note :==
We can't do the function Arrays.contains() to check whether there are duplicate answers in the while loop,because the function take O(n) in worse case,it will causing our algorithm become to O(n^3^) in worse case.

* Space Complexity
Just a bit of variables are allocated ,
Overall space complexity :
**O(1)**

### Submissions on Leetcode
Runtime: **17 ms, 92%**
Memory Usage: **43.1 MB , 51%**

###### tags: `Leetcode` `Medium` `Array`