leetcode15.3sum

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

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

输入一个整数数组，从中找到所有的三个整数组成一个数组，这三个整数的和为0。要求不包括重复的结果

思路一：无hashset or hashmap

这里使用了三个指针。
先对数组进行排序。确定左侧固定的指针，然后移动右侧两个直至找到三个值和为0.如果当前三个指针的值小于0，则将中间的指针右移至下一个不同的值，如果小于0，则将最右侧指针左移至下一个不重复的值。一旦右侧和中间的指针重合，移动左侧指针至下一个不重复的值，并且初始化中间和右侧的指针

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
public List<List<Integer>> threeSum2(int[] nums) {
       List<List<Integer>> result = new ArrayList<List<Integer>>();
    int length = nums.length;
    if(length<3){
        return result;
    }
    Arrays.sort(nums);

    int i = 0;
    while(i<length-2){
        if(nums[i]>0) break;
        int j = i+1;
        int k = nums.length - 1;
        while(j<k){
            int sums = nums[i] + nums[j] + nums[k];
            if (sums==0){
                result.add(Arrays.asList(nums[i], nums[j], nums[k]));
            }
            if (sums<=0){
                //消去左侧重复的数字
                while(nums[j]==nums[++j] && j < k);
            }
            if (sums>=0){
                //消去右侧重复的数字
                while(nums[k--] == nums[k] && j < k);
            }
            
            //消去和当前左指针相同的数字
            while(nums[i] == nums[++i] && i < nums.length - 2);
        }
        
    }
    return result;
}

思路二：有hashmap/hashset

利用hashmap/hashset是为了避开重复的值，但是效率值明显不如上一种方法高

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
public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    HashSet<List<Integer>> set = new HashSet<List<Integer>>();
    for(int i=0;i<num.length;i++)
    {
        for(int j=i+1,k=num.length-1;j<k;)
        {
            if(num[i]+num[j]+num[k]==0)
            {
                List<Integer> l= new ArrayList<Integer>();
                l.add(num[i]);
                l.add(num[j]);
                l.add(num[k]);
                if(set.add(l))
                list.add(l);
                j++;
                k--;
            }
            else if(num[i]+num[j]+num[k]<0)
            j++;
            else
            k--;
        }
    }
    return list;
}