三数之和

问题陈述

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

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

示例：

1
2
3
4
5
6
7
给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路分析

双指针法思路：

  1. 先将数组由小到大排序。
  2. 固定3个指针中的一个k，初始化为数组第一个元素索引0, 然后i=k+1，j=nums.length-1。k<nums.length-2,循环遍历。
  3. 若nums[k]>0,显然后面元素都大于0，直接break。
  4. 若num[i]==nums[++i], 重复元素，直接continue跳过。
  5. 循环过程中判断nums[k]+nums[i]+nums[j]==0? 符合加入list，不符合继续遍历，同样对++i，–j，若重复则直接跳到不重复元素处。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class ThreeSum {
    public List<List<Integer>> getthreeSum(int[] nums){
        Arrays.sort(nums);//对数组进行排序
        List<List<Integer>> list=new ArrayList<>();
        for(int k=0;k<nums.length-2;k++){//固定一个k，判断i，j
            if(nums[k]>0) break;//num[k]>0则直接跳出
            if(k>0&&nums[k]==nums[k-1]) continue;//对k，当前nums[k]和前一个元素nums[k-1]相等的话，为避免重复跳过。
            int i=k+1,j=nums.length-1;
            while (i<j){//i,j相遇则跳出循环
                int sum=nums[k]+nums[i]+nums[j];
                if(sum<0){
                    while (i<j&&nums[i]==nums[++i]);//和小于0，则i++。另外此处的while很巧妙，对nums[i]与下一个元素nums[++i]相等的情况直接跳过。while之后直接到了一个新的nums[i]元素。
                }else if(sum>0){
                    while (i<j&&nums[j]==nums[--j]);//此处j与上同。
                }else {
                    list.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));//else情况sum==0，加入list。
                    while (i<j&&nums[i]==nums[++i]);//继续++i，--j直到i==j。
                    while (i<j&&nums[j]==nums[--j]);
                }
            }
        }
        //多个ArrayList遍历输出
        for (Iterator it = list.iterator(); it.hasNext();) {
            System.out.println(it.next());
        }

        return list;

    }
    public static void main(String[] args){
        int[] nums={-4,-1,-1,-1,0,1,2};
        ThreeSum threeSum=new ThreeSum();
        threeSum.getthreeSum(nums);

    }

}