leetcode: 3Sum

问题描述：

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:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• 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)

原问题链接：https://leetcode.com/problems/3sum/

 

问题分析

    关于这个问题的讨论在之前的一篇文章里已经说过。只不过那只是给出了一个笼统的思路和代码。针对这个具体的问题来说，它有两个额外的限制，一个是要求里面保存的三元组要按照从小到大的索引顺序。另外就是最终保存的结果里不能有重复的项。

    按照之前讨论的思路，我们首先对数组排序。然后取一个元素，再从数组的两头取两个元素，看它们的和与给定元素的差值比较。根据比较结果调整两个元素的移动位置。但是如果单纯的从头取到尾并这么去查找的话，对于给定的元素三元组其实重复查找计算了三次。所以这里需要避免重复的计算。那么该怎么来避免这个重复的计算呢？我们可以从最小的元素的位置来考虑。假设有三个元素a + b + c = 0，其中a是最小的那个元素。那么在后续的计算里要避免这个元素，我们可以在后续的计算范围里缩减到a后面的元素里。也就是说检查是否有符合a + b + c = 0的值范围可以从a后面的元素到数组的末尾。

     另外，数组里面可能有存在重复的元素。这些我们也是可以避免的。我们可以通过判断当前元素的值是否和前一个元素相同来跳过一些不必要的计算和比较。这样也可以提升程序的性能。

     按照前面的讨论，可以得到如下的代码：

 

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for(int i = 0; i < nums.length-2; i++) {
            if(i > 0 && (nums[i] == nums[i-1])) continue; // avoid duplicates
            for(int j = i+1, k = nums.length-1; j<k;) {
                if(nums[i] + nums[j] + nums[k] == 0) {
                    list.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    j++;
                    k--;
                    while((j < k) && (nums[j] == nums[j-1]))j++;// avoid duplicates
                    while((j < k) && (nums[k] == nums[k+1]))k--;// avoid duplicates
                }else if(nums[i] + nums[j] + nums[k] > 0) k--;
                else j++;
            }
        }
        return list;
    }
}

 

评论

1 楼 shihengli2010 2017-04-24  

赞  去重情况很给力。