leetcode 15. 三数之和

一、题目

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

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

二、解法

要使答案不包含重复的三元组，思路是将nums进行排序，并且每次拿出来的元素都不能和上一次的相同。比如[-1,-1,0,1]，如果第一次迭代拿出了两个-1，那么答案中就会有重复。

对于三重循环 \(i,j,k\) ，如果固定了 \(i\) ，随着 \(nums[j]\) 在迭代中增加，为了满足 \(nums[i]+nums[j]+nums[k]=0\) 的条件，必然 \(nums[k]\) 要减小，所以 \(j,k\) 的迭代可以并行发生。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int len=nums.length;
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        for(int i=0;i<len;++i){
            if(i==0||nums[i]!=nums[i-1]){  //a不能取重复值
                int k=len-1;
                for(int j=i+1;j<len;++j){
                    if(j==i+1||nums[j]!=nums[j-1]){  //b不能取重复值
                        while(k>j&&nums[i]+nums[j]+nums[k]>0){
                            --k;
                        }
                        if(k>j&&nums[i]+nums[j]+nums[k]==0){
                            List<Integer> cur=new ArrayList<Integer>();
                            cur.add(nums[i]);
                            cur.add(nums[j]);
                            cur.add(nums[k]);
                            ans.add(cur);
                        }
                    }
                }
            }
        }
        return ans;
    }
}

leetcode 15. 三数之和

原文：https://www.cnblogs.com/livingsu/p/14879148.html