15 三数之和

15 三数之和

此题要求在一维数组中寻找三个数的和为0，首先我们想到的最直接的方法就是 蛮力法 ，直接使用三层循环进行嵌套，查找和为0的三个数，这种方案的是复杂度是，空间复杂度是, 很显然对于这道题这样的时间复杂度是无法接受的。同时考虑到这道题中还要求 不重复 ，因此我们还需要一些额外的检查机制才保证不重复，或者达到去重的效果。

联想到之前做过的两数之和中，我们采用空间换时间的方案，使用哈希表的方法将两数之和的时间复杂度降为。此题中，我们同样能够使用这个方法进行复杂度的降低，但是此时依然存在需要检查重复的问题，同时使用 hashTable 之后的时间复杂度依然为。因此考虑到此，我们可以发现虽然这道题之后将之前的两数之和变为三数之和，但是在求解的方面还是存在着很大的差异，因此我们需要寻找额外的方法进行求解。

对于这道题采用的一个优化办法就是 双指针法 进行优化。由于这道题中的一个要求是 不重复 ，因此我们首先将原数组按从小到大进行 排序 ，排序之后我们就能很容易的通过相邻的元素是否相等这个条件来进行去重。同时，排序之后的元素序列也便于我们使用双指针法进行求解。

排序之后我们为什么能够使用双指针法进行求解？可以发现，如果我们固定了前两重循环枚举到的元素和，那么只有唯一的满足，当我们向后枚举时有，我们需要，那么一定有，也就是说，我们可以从小到大枚举 bb，同时从大到小枚举 cc，即第二重循环和第三重循环实际上是并列的关系。因此保持大的两层循环框架不变，第三层循环我们从右侧开始，向左移动指针。

按照上面的分析，我们可以编写下面的代码，在编写的过程中我们还需要注意一些细节的问题：由于此题中是要求三个数的和为，因此我们在循环中可以使用一些额外的条件，确保在和无法为时，及时的退出当前的求解， 加速整个求解过程。

算法的时间消耗和空间消耗主要来自两个部分，一个是排序，另一个两层循环中的求解。排序过程中的时间复杂度为,空间复杂度为，两层循环求解时时间复杂度为，空间复杂度为。因此算法整体的时间复杂度为，空间复杂度为。

与此题类似的还有四数之和我们也采用同样的办法进行求解。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int first = 0; first < nums.length &&  nums[first] <= 0; ++first) {
            if (first != 0 && nums[first] == nums[first - 1])
                continue;
            int target = -nums[first];
            int third = nums.length - 1;
            if (nums[third] < 0)
                break;
            for (int second = first + 1; second < nums.length; ++second) {
                if (second != first + 1 && nums[second] == nums[second - 1])
                    continue;
                while (second < third &&  nums[second] + nums[third] > target)
                    --third;
                if (second == third)
                    break;
                if (nums[second] + nums[third] ==  target) {
                    List list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}