15. 三数之和

15. 三数之和

题目链接
代码随想录

分析

1. 两数之和 的前车之鉴,我一开始就想到用哈希法,有两种方案,

if (nums[i] == nums[i + 1]) { // 去重操作
    continue;
}

那我们就把三元组中出现重复元素的情况直接 pass 掉了。 例如 {-1, -1 ,2} 这组数据,当遍历到第一个 -1 的时候,判断 下一个也是 -1,那这组数据就 pass 了。
我们要做的是 不能有重复的三元组,但三元组内的元素是可以重复的!
那么应该这么写:

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

这么写就是当前使用 nums[i],我们判断前一位是不是一样的元素,在看 {-1, -1 ,2} 这组数据,当遍历到 第一个 -1 的时候,只要前一位没有 -1,那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。
这是一个非常细节的思考过程
left 与 right 的去重
如果 nums[i]+nums[left]+nums[right] 不为 target,判不判断 nums[right]nums[right-1] 相等或者 nums[left]nums[left+1] 相等其实没什么意义,即使相等,nums[i]+nums[left]+nums[right] 不为 target,还是要移动 left 或者 right,无非是再次出现 nums[i]+nums[left]+nums[right] 不为 target。所以 nums[i]+nums[left]+nums[right] 不为 target 的时候,不需要管 left 和 right 跟他们的下一个元素是否相等。我们只需要判断 nums[i]+nums[left]+nums[right] 等于 target 的时候,left 和 right 跟他们的下一个元素是否相等。
如果 nums[i]+nums[left]+nums[right] 等于 target 的时候, nums[right]nums[right-1] 相等,那就要移动 right,nums[left]nums[left+1] 相等,那就要移动 left,两头都要判断,避免添加重复的三元组合。
判断完之后,还要移动一次,查找下一个三元组合。
其实判断左右指针是否重复,还有一个更加简单的方法,就是,直接把上一次 nums[i]+nums[left]+nums[right] 等于 target 的时候的 nums[left]nums[right] 记下来,下次再出现 nums[i]+nums[left]+nums[right] 等于 target 的情况的时候,对比一下即可,这比让 nums[left]nums[left-1] 对比要更加简单和好理解。

简单总结

其实求两数之和的时候,我们也可以这样做,先对数组进行排序,然后用一个指针指向 nums 的开头,一个指向 nums 的末尾,相向而行,查找和为 target 的组合,但是 1. 两数之和 这道题要求返回元素下标,我们一开始对数组进行排序的时候就打乱了下标,所以只能用哈希表。
如果需要返回下标,那就无法用双指针法,因为双指针法需要排序,会改变下标,这个时候就需要考虑使用哈希法,如果需要返回元素而不是元素的下标,那就先排序,然后再尝试用哈希法。
如果题目要求组合中的所有元素都来自于一个数组,而且一个元素只能用一次,其实这个时候,你就只能用先排序然后双指针的方法了,除此之外没有别的办法可以保证这一点。至于结果去重,那都是额外的附加条件,决定了题目解法的,就是要求组合中的所有元素都来自于一个数组,而且一个元素只能用一次。

解题

public List<List<Integer>> threeSum(int[] nums) {
    //用双指针法
    List<List<Integer>> result = new ArrayList<>();
    // 首先就是要排序
    Arrays.sort(nums);
    for(int i=0;i<nums.length;i++){
        // 如果第一个元素就大于0了,那后面的元素就更大了(排过序了),直接返回
        if(nums[i]>0){
            break;
        }
        if(i>0 &&  nums[i]==nums[i-1]){
            // 跳过重复元素
            continue;
        }
        int left = i+1,right=nums.length-1;
        while(right>left){
            int sum = nums[i]+nums[left]+nums[right];
            if(sum<0){
                left++;
            }else if(sum>0){
                right--;
            }else{
                List<Integer> combination = Arrays.asList(nums[i],nums[left],nums[right]);
                result.add(combination);
                //跳过重复元素
                while((right-1)>left && nums[right] == nums[right-1]){
                    right--;
                }
                while(right>(left+1) && nums[left] == nums[left+1]){
                    left++;
                }
                // 跳过重复元素之后,两个指针都要移动
                right--;
                left++;
            }
        }
    }
    return result;
}

另一种去重 left 和 right 的方法

public List<List<Integer>> threeSum(int[] nums) {
    // 因为我们要返回元素本身,而不是索引,所以可以进行排序
    // 排序之后,我们就可以使用双指针
    // 然后移动一个元素,在后面的范围里面用双指针法,找组合,
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for(int i=0;i<nums.length;i++){
        if(nums[i]>0){
            break;
        }
        // 如果当前元素跟上一个元素相同,则直接跳过查找
        if(i>0 && nums[i]==nums[i-1]){
            continue;
        }
        int target = 0- nums[i];
        int left = i+1,right =  nums.length-1;
        // 记住上一次的left和right,帮助去重
        Integer lastLeftEle = null;
        Integer lastRightEle = null;
        // 因为我们要找两个元素,区间只有一个元素是不行的
        while(left<right){
            int nowSum = nums[left]+nums[right];
            if( nowSum<target ){
                left++;
            }else if( nowSum>target ) {
                right--;
            }else{
                if((lastLeftEle == null && lastRightEle ==null) || (lastLeftEle!=nums[left] &&  lastRightEle!=nums[right]   )  ){
                    List<Integer> combination = new ArrayList<>();  
                    combination.add(nums[i]);
                    combination.add(nums[left]);
                    combination.add(nums[right]);
                    result.add(combination);
                    lastLeftEle = nums[left];
                    lastRightEle = nums[right];
                }
                right--;
                left++;
            }
        }
    }
    return result;
}

相关题

1. 两数之和
344. 反转字符串
18. 四数之和 - 待复习