当前位置：首页 > article >正文

BM54-三数之和

article 2024/9/20 19:37:23

题目

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

数据范围：0≤n≤1000，数组中各个元素值满足 ∣val∣≤100。

空间复杂度：O(n^2)，时间复杂度 O(n^2)。

注意：

三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
解集中不能包含重复的三元组。

例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10)。

示例1

输入：[0]

返回值：[]

示例2

输入：[-2,0,1,1,2]

返回值：[[-2,0,2],[-2,1,1]]

示例3

输入：[-10,0,10,20,-10,-40]

返回值：[[-10,-10,20],[-10,0,10]]

思路1：双指针

实现版本1：

直接找三个数字之和为某个数，太麻烦了，我们是不是可以拆分一下：如果找到了某个数a，要找到与之对应的另外两个数，三数之和为0，那岂不是只要找到另外两个数之和为−a？这就方便很多了。

因为三元组内部必须是有序的，因此可以优先对原数组排序，这样每次取到一个最小的数为a，只需要在后续数组中找到两个之和为−a就可以了，我们可以用双指针缩小区间，因为太后面的数字太大了，就不可能为−a，可以舍弃。

具体做法：

step 1：排除边界特殊情况。
step 2：既然三元组内部要求非降序排列，那我们先得把这个无序的数组搞有序了，使用sort函数优先对其排序。
step 3：得到有序数组后，遍历该数组，对于每个遍历到的元素假设它是三元组中最小的一个，那么另外两个一定在后面。
step 4：需要三个数相加为0，则另外两个数相加应该为上述第一个数的相反数，我们可以利用双指针在剩余的子数组中找有没有这样的数对。双指针指向剩余子数组的首尾，如果二者相加为目标值，那么可以记录，而且二者中间的数字相加可能还会有。
step 5：如果二者相加大于目标值，说明右指针太大了，那就将其左移缩小，相反如果二者相加小于目标值，说明左指针太小了，将其右移扩大，直到两指针相遇，剩余子数组找完了。

注：对于三个数字都要判断是否相邻有重复的情况，要去重。

代码1.1

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        int n = num.length;

        //不够三元组
        if(n < 3) {
            return res;
        }

        //排序
        Arrays.sort(num);

        for(int i = 0; i < n - 2; i++) {
            if(i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            //后续的收尾双指针
            int left = i + 1;
            int right = n - 1;
            //设置当前数的负值为目标
            int target = -num[i];

            while(left < right) {
                //双指针指向的二值相加为目标，则可以与num[i]组成0
                if(num[left] + num[right] == target) {
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(num[i]);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    res.add(temp);
                    while(left + 1 < right && num[left] == num[left + 1]) {
                        //去重
                        left++;
                    }
                    while(right - 1 > left && num[right] == num[right - 1]) {
                        //去重
                        right--;
                    }
                    //双指针向中间收缩
                    left++;
                    right--;
                } else if(num[left] + num[right] > target) {  //双指针指向的二值相加大于目标，右指针向左
                    right--;
                } else {  //双指针指向的二值相加小于目标，左指针向右
                    left++;
                }
            }
        }
        return res;
    }
}

时间复杂度：O(n^2)，排序的复杂度为O(nlog2n)，查找三元组的复杂度为O(n2)。
空间复杂度：O(1)，res属于必要空间，不属于额外空间，无其他辅助空间。

实现版本2：

对数组长度进行特判。
排序。

num[i] > 0说明后面的三数和不可能等于0。
对于重复元素跳过。
左指针left = i + 1，右指针right = len - 1
当nums[i] + nums[left] + nums[right] == 0执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 left,right 移到下一位置，寻找新的解。
如果和<0，left++;
如果和>0，right--；

代码1.2

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        //存放最终答案的二维数组
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        int len = num.length;

        //特判：长度<3的数组不满足条件
        if (len < 3) {
            return ans;
        }

        //排序O(nlogn)
        Arrays.sort(num);

        for (int i = 0; i < len; i++) {
            //如果nums[i]已经大于0，就没必要继续往后了，因为和就是0啊
            if (num[i] > 0) {
                return ans;
            }
            //注意考虑越界i>0,主要功能是排除重复值
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }
            //声明指针
            int cur = num[i];
            int left = i + 1;
            //从尾部开始
            int right = len - 1;
            
            while (left < right) {
                //满足条件的三数和
                int tp_ans = cur + num[left] + num[right];
                //如果已经找到和为0
                if (tp_ans == 0) {
                    //创建一个数组，并将满足条件的三元素放进去
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(cur);
                    list.add(num[left]);
                    list.add(num[right]);
                    //将最终的结果存入答案数组ans中
                    ans.add(list);
                    //判断是left指针指向是否重复
                    while (left < right && num[left] == num[left + 1]) {
                        left++;
                    }
                    //判断是right指针指向是否重复
                    while (left < right && num[right] == num[right - 1]) {
                        right--;
                    }
                    //移动指针
                    left++;
                    right--;
                } else if (tp_ans < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return ans;
    }
}

时间复杂度：O(n^2)。
空间复杂度：O(1)。

思路2：哈希表

利用哈希表特性，对符合条件的三元组进行去重处理。

代码2

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        //存放答案的集合
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        int len =  num.length;

        //排序O(nlogn)
        Arrays.sort(num);

        //哈希表去重
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            map.put(num[i], i);
        }

        //若干变量声明
        int L, M, R;
        for (int i = 0; i < len; i = map.get(L) + 1) {
            //指定L的值
            L = num[i];
            //注意里层循环从i+1开始
            for (int j = i + 1; j < len; j = map.get(M) + 1) {
                M = num[j];
                //注意一下，这里是个容易错的细节..
                R = -L - M;
                if (R < M) {
                    break;
                }
                if (map.get(R) != null && map.get(R) > j) {
                    //创建一个数组，并将满足条件的三元素放进去
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    list.add(L);
                    list.add(M);
                    list.add(R);
                    //将最终的结果存入答案数组ans中
                    ans.add(list);
                    //ans.add(Arrays.asList(L,M,R)); 不知道为什么这种写法在牛客平台编译过不了
                }
            }
        }
        return ans;
    }
}

查看全文

http://www.kler.cn/news/18075.html