【数据结构与算法】三数之和

大家好，欢迎来到IT知识分享网。

这是一道LeetCode上经典的题目，是第一题（两数之和）的变形，仅此小记一些解题思路。 

  拿到题目的第一时间，可以看下底部的提示，判断数据范围是多大，从而判断我们能用到哪些数据结构来解决问题，从图上可以看到，数组的最大长度是3000，大概是10^3，我们可以用复杂度为O(N ^ 2) or O(N ^2logN)的方法来尝试解决问题！

  其次呢，对于这个题目，大家能想到最直接的的办法应该三个for暴力求解吧hh（🐶），不过这样在上一步分析时间复杂度的时候是明显不行的，那么这个时候就是我们要做的，怎么把复杂度降低。

   接下来就说下我个人的思路：

1. 三数之和(n数之和类型的题目)，我会通过固定一个数a、用双指针指向b、c求符合条件的组合，这样可以做到第一层for遍历a => 复杂度O(N)、双指针遍历数组里的其他元素所需的时间复杂度也为O(N)（ps：这样的思路也是通过做题了解到的，然后理解并记忆，如果说没有学方法，脑海里能生成解题的方法，我觉得是比较困难的，引用逆哥的一句话：“好比你没学过一元二次方程，却在求他的解”，所以算法还是多刷题，多总结）；
2. 然后呢，这个题目是要求a+b+c = 0；而且题目返回的结果是元素值，而不是其所在的下标，所以我们可以通过对给出的数组nums进行排序，得到一个具有单调性的数组，这样的做法必要性在，我们可以通过规定好指针如：i < left < right（其中i指向a的指针，left和right分别代表再每一次求解过程区间范围），这样他们同样是具有单调性的，这对于我们进行结果的去重是很有帮助的；
3. 接下来无非就是这样的做法，遍历数组（选a）、设定区间（left、right）、区间查找条件符合（此时需要注意去重）步骤，当你找到一个符合条件的时候就万事大吉了吗？显然不是的，这个时候要去变化left和right的值，假如不进行去重操作，如举一个例子
   
   

所以，我们最后的代码是这样的：

class Solution { 
    public List<List<Integer>> threeSum(int[] nums) { 
    // 数组进行排序 Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); if(nums[0] > 0) return res; for(int i = 0; i < nums.length - 2; i++){ 
    // 因为后面的指针所指向的数组是直接大于0的 if(nums[i] > 0) break; // 此时前面的元素已经列出所有组合 if(i >= 1 && nums[i] == nums[i-1]) continue; // 左右指针(怎么制定！！！！！) int left = i+1, right = nums.length - 1; while(left < right){ 
    int sum = nums[i] + nums[left] + nums[right]; if(sum == 0){ 
    // 找到结果 res.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right]))); left++; right--; // 去重 // 判断当前left是否跟上一个left是一样的 while(left < right && nums[left] == nums[left-1]) left++; // 判断当前right是否跟上一个right是一样的 while(left < right && nums[right] == nums[right+1]) right--; }else if(sum < 0){ 
    left++; while(left < right && nums[left-1] == nums[left]) left++; }else{ 
    right--; while(left < right && nums[right+1] == nums[right]) right--; } } } return res; } } 

题目链接：15、三数之和