leetcode 之4Sum问题

问题描述：

Given an array S of n integers, are there elements a,b,c, andd inS such thata +b +c +d = target?

Find all unique quadruplets（四元组） in the array which gives the sum of target.

Note（提示）: The solution set must not contain duplicate(重复的，完全一样的) quadruplets. 、

例子：

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

问题来源：4Sum  (详细地址：https://leetcode.com/problems/4sum/#/description）

思路：这道题的思路其实和2Sum,3Sum的思路几乎是一致的，3Sum是固定住一个数，动用两个指针，从而转化为2Sum问题； 4Sum问题也是类似的：

            1) 第一次固定住一个数，在这记为before(因为待会还要标记当前值，所以在此将它标记为before,不够好像有点不符合命名习惯)，传递给threeSumForFourSum函数;

            2)紧接着再次固定住一个整数，在此当前值就记作了now（在这有点符合命名习惯了吧）,传递给twoSumForFourSum函数；

            3)接着就是处理2Sum问题了，主要是动用首尾两个指针（在这记作low和high），然后将这两个指针往中间靠拢求解就可以了。

代码：

主体部分：

转化为threeSumForFourSum函数：

转化为twoSumForFourSum函数求解：