# 15 3Sum

15. 3SumMedium4579530FavoriteShare

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]
]

題目是找出該int[] 裡3個加總為0的可能，不包含重複。這題我沒有解出來，我沒有解決重複的那塊，但我也不是很清楚這個類似的Ksum的方法。看人家的解法，只能大約的推測，但實際這樣背後的數學原理，我不是很懂。

程式碼:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List< List<Integer> > list = new ArrayList< List<Integer> >();
        // Set<List<Integer>> setOfListOfInteger = new HashSet< List<Integer> >();
        int start = 0;
        int end = 0;
        for(int i = 0; i < nums.length-2 ; i++){
            
            //正負2邊，只計算正的或負的，如 -2 0 2 這才可能加總為0 ;如2 4 6 這跟本不可能加總為0
            if(nums[i] > 0){
                // System.out.println("nums[i] > 0 , i = " + i + " , nums[" + i + " ] = " + nums[i] );
              continue;
            }
            
            //去掉重複的去掉 -1,-1,0,0,2,9 -1在index 0 及index 1 ，只會處理一個。
            if (i > 0 && nums[i] == nums[i - 1]){
                // System.out.println("i > 0 && nums[i] == nums[i - 1] , i = " + i + " , nums[" + i + "] = " + nums[i] );
              continue;  
            }
            
            //start end都要重新再重置
            start = i+1;
            end = nums.length-1;
            while(start < end){
                if(nums[start] + nums[end] < -nums[i]){
                    start++;
                }else{
                    if(nums[start] + nums[end] > -nums[i]){
                        end--;
                    }else{
                        list.add( Arrays.asList(nums[i] , nums[start] , nums[end]) );
                        start++;
                        end--;
                        
                        //避免重複的值
                         while(start < end && nums[start] == nums[start-1]){
                            start++;
                        }
                        while(start < end && nums[end] == nums[end+1]){
                            end--;
                        }
                    }                    
                }
            }
        }
        
        
        return list;
    }
}