Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:[  [-1, 0, 1],  [-1, -1, 2]]

 Idea: Simplify this problem from O(n^3) to n square by using two pointers

 iterate i and j = i+1 and k = n-1 (j and k are two pointers we would use)

class Solution {    public List
       
        
         > threeSum(int[] nums) {        Arrays.sort(nums);        List
         
          
           > res = new ArrayList
           
            
             >(); //two pointers //set i and move j and k (if sum <0 j++ else k--) for(int i = 0; i
             
               temp = new ArrayList
              
               (); temp.add(nums[i]); temp.add(nums[j]);temp.add(nums[k]); //if(!res.contains(temp)) //why add this make TLE **** res.add(temp); ++j; //System.out.println("wei"); while (j < k && nums[j] == nums[j-1]) ++j; **** }else if(nums[i] + nums[j] + nums[k] < 0){ j++; }else { k--; } } } return res; }}
              
             
            
           
          
         
        
       

 1.avoid the duplicate elements -1 -1 (for the same values, there are same results)

2. avoid using contains because of O(n), that is the reason why we need check the duplicate elements manually instead of using contains

 Solution 2: using hashmap: n^2*lgn

 

class Solution {    public List
       
        
         > threeSum(int[] nums) {        List
         
          
           > res = new ArrayList
           
            
             >(); Arrays.sort(nums); for(int i = 0; i < nums.length; i++){ if(i!=0 && nums[i-1] == nums[i]) continue; Set
             
               set = new HashSet<>(); // no duplicate elements for(int j = i+1; j
              
                temp = new ArrayList<>(); temp.add(nums[i]);temp.add(nums[j]);temp.add(-nums[i]-nums[j]); res.add(temp); //avoid the duplicate elemnts ++j; while(j < nums.length && nums[j-1]==nums[j]) j++; --j; } if(j
              
             
            
           
          
         
        
       

hashset

how to using two loop to represent three numbers.

1. treat all nums[j] as c(the third elemnts)

2. As a+b+c = 0, c = -a-b, we need find a and b to satisfy the requirement

 

Great reference: https://fizzbuzzed.com/top-interview-questions-1/#twopointer -- speak human language nice.