LeetCode: L15 三数之和

2021-10-04/2021-10-05 | 0 评论 | 1,016 浏览

题目

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一: 暴力解法

class Solution {
    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> rs = new ArrayList<>();
        for (int i=0 ;i<nums.length-2;i++) {
            for(int j = i+1;j<nums.length-1;j++){
                for(int k = j+1;k<nums.length;k++){
                    if(nums[i] + nums[j] + nums[k] == 0){
                        List<Integer> item = new ArrayList();
                        item.add(nums[i]);
                        item.add(nums[k]);
                        item.add(nums[j]);
                        Collections.sort(item);
                        boolean has = false;
                        for(List<Integer> it : rs){
                            if(it.get(0) == item.get(0) && it.get(1) == item.get(1)){
                                has = true;
                            }
                        }
                        if(!has){
                            rs.add(item);    
                        }
                    }
                }
            }
        }
        return rs;
    }
}

解法二: 排序+遍历加二分查找

排序的复杂度为 O(NLogN) , Java 的基本类型是使用内置的快速排序

遍历所有的区间. 复杂度为 O(N^2) ,而每一个区间的查找需要二分复杂度:LogN,整体遍历区间的复杂度为: N^2*LogN

整体复杂度为: (N^2+N)LogN

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> rs = new ArrayList<>();

        Arrays.sort(nums);
       
        for(int i=0;i<nums.length-2;i++){
            if(i>0 && nums[i] == nums[i-1]){continue;}
            for(int j =nums.length-1;j>i+1;j--){
                if(j<nums.length-1 && nums[j] == nums[j+1]){continue;}
                int sum = -(nums[i]+nums[j]);
                int lo = i+1, hi=j-1;
                int k = -1;

                while(lo<=hi){
                    int mid = lo + (hi -lo)/2;
                    if(sum == nums[mid]){
                        k = mid;
                        break;
                    }else if (sum > nums[mid]){
                        lo = mid+1;
                    }else {
                        hi = mid-1;
                    }
                }

                if(k>=0){
                    List<Integer> item = new ArrayList();
                    item.add(nums[i]);
                    item.add(nums[k]);
                    item.add(nums[j]);

                    rs.add(item);
                }
            }
            int o = nums[i];
           
        }
        return rs; 
    }
}

解法三: 排序+双指针解法

此方法是先固定一个元素. 然后再找此元素右边的两元素. 而此方法与官方题解的区别在于. 寻找第二数时,没有固定第二数. 即两指针同时往右边逼近.

首先证明这个同时移动的正确性.

N = nums.length;
假设有如下场景. first为:a[i-1]接下来从 i 到 j(j 初始化为 N-1)
target=-a[i-1],target值为待寻找的i,j的和, target == a[i]+a[j]

a[i-1] ,  
a[i ]  , a[i+1] , a[i+2] , ... , a[j-2] , a[j-1] , a[j]

证明一定能找到需要`l`和`r`

证:

假设存在这样的的l和r,且: l >= i ,r<=j
lo,hi指针的移动方法:
- lo,hi分别初始化为i,j
- 如果 a[lo]+a[hi]<target 右移lo;
- 如果 a[lo]+a[hi]>target 左移hi;
lo 一定是往右移动
hi 一定是往左移动
如果存在这样的l,r则一定会有一边会先到目标下标.
- 假设 lo 先到达l,此时一定a[lo]+a[hi]>target , 此时一定会接着移动hi往左.直到hi == r ,此时找到了假设的 l,r
- 假设 hi 先到达r,此时一定a[lo]+a[hi]<target , 此时一定会接着移动lo往右.直到lo == l ,此时找到了假设的 l,r
 如上: 如果存在一对l,r一定会被找出来.

证明能找到所有的`l` 和`r`

特征: 所有的l,r对不可能没有交叉 ,如 l1,r1 l2,r2 ,如左边所述. 如果 r1<l2 则12+r2 > l1+r1 ,因为右边的两个数都更大.
特征: 如上一条,同时也不会交叉: 如 l1,l2,r1,r2 ,这样同样会得到 `12+r2 > l1+r1 ,因为 l与 r 的两个值都分别大于第一对.
结论: 如果存在多个满足条件的. 那必须是 l 大一点的时候,r 必定小一些. 即如: l1,l2,r2,r1如此一定会从外到内的遍历出所有的数对即: 找到一对l,r时,可以继续往中间搜索另外可能存在的数对.

证明. 确定`first`为 `a[i]`的时候,只需要往右遍历.

这个其实不用证明,一般我们多重循环暴力枚举的时候i,j,k 的初始化都是把 j=i+1,k=j+1往右遍历的.
-反证: 如果在遍历a[i]的时候存在a[i-x]和 a[i+y]和为零. 那这三个数:a[i-x],a[i],a[i+x]那这个值可以在固定a[i-x]的时候可以往右遍历出来.因此不必回头看.
代码如下:

import java.util.*;
class Solution {
   
    // 双指针两头移动
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> rs = new ArrayList<>();
        int N = nums.length;
        Arrays.sort(nums);
        for(int i =0;i < N-2;i++){
            if(i>0 && nums[i] == nums[i-1]) { continue;}
            if (nums[i] > 0) break;
            int lo=i+1;
            int hi=N-1;
            int target = -nums[i];
            while(lo<hi){
                int sum =nums[lo]+nums[hi];
                if(sum == target) {
                    List<Integer> item = new ArrayList();
                    item.add(nums[i]);
                    item.add(nums[lo]);
                    item.add(nums[hi]);
                    rs.add(item);
                    int lo1 = lo+1;
                    while(lo1<hi && nums[lo1] == nums[lo]) { ++lo1; }
                    lo = lo1;

                    // 优化理由: 找到相等的时候, hi 亦必定下移一次
                    int hi1 = hi-1;
                    while(hi1>lo && nums[hi1] == nums[hi]){ hi1--;}
                    hi = hi1;
                    continue;
                } 
                //int sum =nums[lo]+nums[hi];
                if(sum > target){
                    int hi1 = hi-1;
                    // 此处的多移可以优化算法效率
                    while(hi1>lo && nums[hi1]+nums[lo] > target){ hi1--;}
                    hi = hi1;
                }else if (sum < target) {
                    int lo1 = lo+1;
                   // 此处的多移可以优化算法效率
                    while(lo1<hi && nums[lo1] + nums[hi] < target) { lo1++; }
                    lo = lo1;
                }  
            }
        }
        return rs;
    }
}

复杂度分析:

排序: NLogN

双指针查找 N^2

整体复杂度: NLogN+N^2

题目