三个数之和

三个数之和

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解决思路

• 暴力方法
  算法复杂度是o(n^3)
• 双指针方案
  算法复杂度是o(n^2)
  在这里我们不使用暴力方法，暴力方法也比较简单

双指针方案

思路图解

• 首先我们我们对数组进行遍历：
  
• 我们再定义两个指针分别指向后边子数组的起始下标和结束下标位置：

注意地方：
1.j的下标边界是[0,nums.length-3]
2.如果nums[j] ==nums[j-1],那么就跳过此次循环，这是为什么呢？
因为数组排序了啊，如果j在此处就符合，那么必出现重复的情况，不符合题目要求。

• 问题解决
  nums[j]+nums[i]+nums[k]?等于target
  分情况讨论：
  • 如果上面三个之和大于target就将k–
  • 如果上边三个数之和小于target就将i++
  • 如果等于就将结果添加到集合中

代码实现：

public List<List<Integer>> threeSum(int[] nums) {
      List<List<Integer>> result = new LinkedList<>();
      Arrays.sort(nums);
      for (int k = 0; k <nums.length-2 ; k++) {
         if(nums[k] > 0){
           continue;
         }
      if(k>0&&nums[k]==nums[k-1]){
        continue;
      }
       int i = k+1,j = nums.length-1;
       while (i<j){
        int sum = nums[k]+nums[i]+nums[j];
        if(sum<0){
          i++;
        }else if(sum>0){
          j--;
        }else {
          List<Integer> list = new LinkedList<>();
          list.add(nums[k]);
          list.add(nums[i]);
          list.add(nums[j]);
          result.add(list);
          while(i<j&&nums[i]==nums[i+1]){
            i++;
          }
          while (i<j&&nums[j]==nums[j-1]){
            j--;
          }
           i++;
           j--;
        }
      }
    }
    return result; 
}

总结

算法思路很清晰，只需要应用两个指针进行夹逼，最后得到最后的结果。算法实现复杂度就是o(n^2),降低了一般方法的复杂度。

本文作者： JanLee
本文链接： http://yoursite.com/2019/08/25/三个数之和/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

-------------本文结束感谢您的阅读-------------

赏

谢谢你的打赏！！

微信