18.4Sum

思路：

四个数相加的和等于目标，且要去重复

代码：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();//数组初始化
       
       if(nums.length<=3 || nums==null){
           return result;
       }
       
       Arrays.sort(nums);//数组排序，方便后面进行去重复

       for(int i =0;i<nums.length;i++){
           if( i>0 && nums[i]==nums[i-1] ) continue; //注意：必须把i>0写在&& nums[i]==nums[i-1]的前面，因为i>0这个条件就是为了让nums[i-1]取值时不会发生越界错误，如果把i>0放到&&后面了就毫无意义了。
           for(int j = i+1;j<nums.length ;j++){
               if(nums[j]== nums[j-1] && j>i+1) continue;
               int begin = j+1;
               int end = nums.length-1;
               while(begin <end){
                   int sum = nums[i]+nums[j]+nums[begin]+nums[end];
                   if(sum == target){
                       List<Integer> list = new ArrayList<>();
                       list.add(nums[i]);
                       list.add(nums[j]);
                       list.add(nums[begin]);
                       list.add(nums[end]);
                       result.add(list);
                       begin++;
                       end--;
                       while(begin<end && nums[begin]==nums[begin-1]) begin++;
                       while(begin<end && nums[end]== nums[end+1]) end--;
                   }else if(sum>target){
                       end --;
                   }else{
                       begin++;
                   }
                   
               }
           }
       }
       return result;
    }
}