• 思路： 遍历+双指针
  四数之和是三数之和的升级版，思路一脉相承，大体是通过遍历依次控制住数组中的每个元素，在每次循环过程中使用双指针来对整个数组的某几位数进行相加之和的检索判断。只不过四数之和比三数之和要多一个循环，可以认为是在三数之和循环的基础上外套了一层循环来实现四个数相加之和的实现。但是编程的实现往往才是难点，细节主要有两点，为了减少不必要遍历次数的剪枝和为了实现返回数组中没有重复答案的去重。

• 为什么需要剪枝（剪枝的意义）？
  因为代码的底层思路是双指针，左指针在最左端，右指针在最右端，四数之和如果大于target则right--，反之则left++。我们发现由于双指针中的right是从最右端也就是最大元素开始遍历的，那么如果此时target的值对于数组中的元素来说过小，则right会毫无意义的多次--才能达成四数之和等于target的要求（甚至可能出现数组中只需要一个数就大于target的情况，也就是说遍历到头一无所获），白白浪费了时间，这时候如果可以在遍历之前提前进行一次判断，如果数组中的最小的四个数的和都大于target的值，那么就可以直接跳出整个循环，可以节省时间提高效率，所以剪枝是对代码的一个优化操作。

• 第一次剪枝

 if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target){
                break;
            }

这次操作的想法是，如果我此时最小的四个数之和都要大于target，那么剩下的数也就没有继续遍历的必要了，可以直接跳出最外层循环，return最终数组了。

• 第二次剪枝

第二次剪枝发生在第二层循环中（即三数循环之中,双指针之外），目的仍然是对于target可能过小这一种情况的优化。

if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2]>target){
                    break;
                }

注意
第二次剪枝中如果判断target的值过小，则会break，跳出本循环，但是和第一次剪枝操作的不同之处在于：第一次剪枝操作会直接跳出最外层循环，return结束程序了，但第二次剪枝操作则是跳出内循环，继续外循环中下一个元素的循环，不会结束自身的循环（继续外循环中i=i+1时的内循环）也不会结束程序。

• 疑问（1）: 两次剪枝操作是否重复，即第二次剪枝操作是否还有必要?
  结论：部分重复了，但还是有必要。
  这个疑问主要在于大家看到了在第二次剪枝操作的第一次执行和第一次剪枝操作的第一次执行一摸一样。即都是对数组中的前四个元素（索引为0，1，2，3）之和进行了一次判断，很明显重复了呀。确实重复了，但是之后它会很好的执行减少无意义的循环遍历次数的工作，比如nums[]={1,2,3,4,5,6,7},target=11.这种情况下最外层第一次剪枝操作会顺利通过（1+2+3+4=10正好小于target11），但之后进入内循环中后的情况就是无意义的遍历了，right会一直 ' -- ' 直到内循环结束，而且这时候已经运行到了内循环之中外循环中的剪枝操作无法再进行判断了，所以我们需要第二层循环（内循环）中也有一个剪枝操作来减少这种无意义的遍历，如果target过小则直接舍弃，跳出此次循环，进入最外层循环的下一个元素遍历中，这就是第二次剪枝。所以第二次剪枝虽然和第一次剪枝会有一次重复但还是有意义的，有存在必要的。
• 疑问（2）： 为什么只考虑target的值过小的时候的优化，target的值过大的时候的优化呢？
  结论：虽然题解没有写，但是我认为应该写上去，而且两种情况的剪枝操作实现起来细节不同。
  两种情况的思路是不一样的，如果i的某次循环中的四个最小的元素之和还要大于target则break，也就说这次剪枝判断是要执行多次的，因为i是从最小值也就是数组的最左边开始移动遍历的，他的四数之和的最小值是会随着遍历次数的增大而增大的！也就是说会存在一种情况即：刚开始遍历的时候四数之和的最小值都小于target，那么满足条件，可以继续执行，如果到某一次循环的时候四数之和的最小值大于target了，那么后面的都是不满足条件的，就break出去。
  但是四个最大的元素之和的小于target这种情况是只执行一次的！target过大的这种情况判断则是一锤定音的，只执行一次的，因为四数之和的最大值并不会随着遍历次数的增加而增大！他永远都是最右边的那四个数相加，所以我认为题解可以进行优化，也就是在进入循环遍历之前就进行一次target是否过大的判断，如果过大则直接结束程序。
  //剪枝判断是否此次循环中target过大程序如下：

n=nums.length-1;
if((long)nums[n]+nums[n-1]+nums[n-2]+nums[n-3]<target){
                return quadruplets;//quadruplets为最终返回数组
            }

• 去重的意义
  去重有两类，有两种意义。
  第一类去重：目的是为了减少因为数组中的重复元素导致的循环遍历比如nums[]={1,1,2,3,4,5,6},这种情况下可以看到第一次和第二次循环的时候情况是一模一样的，如果可以只执行一次就好了，代码实现如下：

if(i>0&&nums[i]==nums[i-1]){
                continue;
            }

注意
我们不可以写成nums[i]==nums[i+1]这样，因为nums[i+1]其实就是nums[j],如果这样子写的话，我们的目的就从去重变成了避免目标数组中出现相同元素的情况了，使得最终答案收集不全，比如这种情况: nums[]={1,1,5,20,30},target=27。很明显这种情况下 1 1 5 20是满足条件的一组答案，但是由于第一个元素和第二个元素相等了，就被nums[i]==nums[i+1]这种判断给捕获筛去（continue）了， 所以要写成nums[i]==nums[i-1]这样来确保nums[j]和nums[i]相等时依然可以继续执行下去。（记得确保i>0,否则会报数组越界异常）
第二类去重：目的是为了减少不必要的循环次数，是一种优化

 if((long)nums[i]+nums[length-3]+nums[length-2]+nums[length-1]<target){
                continue;
            }

这种去重的思路是：判断在此时i的索引情况下的最大四数之和是否还要小于target的值。
如果小于，那么后面就不用继续执行（continue）了，继续下一次循环，试一试i=i+1时是否满足条件。
去重的总结（1）：通过第一类去重的使用，去掉了由于数组中存在相同元素导致的多余循环次数（还能使得答案数组中可以有相同的元素）
比如nums[]={1,1,1,2,2,2,3,3,3,4,4,4,5,6}.这种情况下如果不去重那么肯定会有多次一模一样的循环。
第一次去重（最外层循环中的去重）中nums[i]==nums[i-1]{continue},确保了nums[i]和nums[j]元素的值相等的时候依然可以正常运行下去不会被continue。
第二次去重（内层循环的去重）中nums[j]==nums[j-1]{contiue},确保了第二个元素和第三个元素的值相等的时候依然可以正常运行下去。
由于nums[left]与nums[right]的值是否相等都不会被continue，所以我们可以说通过第一类去重分别在两个循环中的两次使用来，答案数组中的四个元素的值全部相等的情况依然可以被我们囊括其中。
去重的总结（2）：通过第二类去重的使用，减少了在某个特定循环次数下无意义的循环次数（在i=n时，target过大导致的无意义循环）
通过第二类去重分别在两个循环中的使用，使得无意义遍历可以快速结束，节省时间，是一种优化。
总结
四数之和是对三数之和的拔高，代码实现上它在三数之和上又加了层循环。它不仅考察了去重还考察了剪枝，其中去重有两类，在两层循环中每一类均有使用，一共使用了四次。剪枝有一类（按题解），在两层循环中均有使用，使用了两次。
优化：针对如果target过大这种情况的剪枝（避免在第一次循环的第二个去重操作中的多余循环，节省时间）：
操作：在进入循环之前，代码之初就进行一次判断，判断是否target对于数组来说过大，如果是，那么就直接return

if(((long)nums[n.length-1]+nums[n.length-2]+...nums[n.length-4])<target){
    return quadruplets;
}

• 思路来源：对于剪枝总是针对target过小这种情况进行优化的引申思考。即是否可以针对target过大来进行优化呢？答案是可以。
  个人感悟
  本以为已经会了，但是在写题解的时候又有了新的收获，提出了自己的优化思路，自己与自己辩论，感觉很快乐，哈哈哈。（花了我两个半小时从下午写到天黑QAQ）
  题解代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>>quadruplets=new ArrayList<List<Integer>>();
        if(nums==null||nums.length<4){
            return quadruplets;
        }
        Arrays.sort(nums);
        int length=nums.length;
        if(((long)nums[length-1]+nums[length-2]+nums[length-3]+nums[length-4])<target){
                return quadruplets;
        }
        for(int i=0;i<length-3;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target){
                break;
            }
            if((long)nums[i]+nums[length-3]+nums[length-2]+nums[length-1]<target){
                continue;
            }
            for(int j=i+1;j<length-2;j++){
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2]>target){
                    break;
                }
                if((long)nums[i]+nums[j]+nums[length-2]+nums[length-1]<target){
                    continue;
                }
                int left=j+1,right=length-1;
                while(left<right){
                    long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum==target){
                        quadruplets.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left<right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        left++;
                        while(left<right&&nums[right]==nums[right-1]){
                            right--;
                        }
                        right--;
                    }else if(sum<target){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
}