提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【刷题计划】三数之和

输入
2023-03-15 22:03:59 时间

1三数之和

通过前文两数之和算法练手，感觉还好，有了一点做题感觉，

今天看到了这个三数之和的题目，就迫不及待了做了起来

2三数之和

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

示例 ：

输入：nums = [5,12,6,3,9,2,1,7] target= 13 输出：[[5,6,2],[5,1,7],[3,9,1]]

思路1

有了前文两数之和题目的铺垫，首先想到了固定某一个值，然后求两数之和为剩余值

比如固定住第一个数字5，然后在其他数字中求两数之和为13-5=8的两个数字

public static List<List<Integer>> threeSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        //两数之和过程
        Map<Integer, Integer> data = new HashMap<>();
        for (int j = i + 1; j < nums.length; j++) {
            int d2 = need - nums[j];
            if (data.containsKey(d2)) {
                result.add(Arrays.asList(nums[i], nums[j], d2));
            }
            data.put(nums[j], j);
        }
    }
    return result;
}

这种方式是可以完成此题，但是算法复杂度是O(n²)，空间复杂度是O(n)(用于多次构建两数之和map)

同时有点硬靠两数之和解法的嫌疑

缺点是空间复杂度偏大，想办法把空间复杂度降低到O(1)

思路2

其实三数之和已经失去了用hash快速定位的优势，如果硬板前面解法反而浪费了空间，需要多次构建hash表

此时不必拘泥于前面的解法

采用排序+双指针解法

public static List<List<Integer>> threeSum2(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        //查找剩余两数之和为need的数字
        //由于是已经排序的数组，可以使用头尾两个指针来控制，之和的大小
        for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) {
            //如果两数之和大于need，所以右指针左移，也就是向着变小的方向移动k--才有可能找到答案
            //如果两数之和小于need，所以左指针右移，也就是向着变大的方向以移动j++
            while (j < k && nums[j] + nums[k] > need) {
                k--;
            }
            //遍历结束
            if (j == k) {
                break;
            }
            //发现满足条件的答案
            if (nums[j] + nums[k] == need) {
                result.add(Arrays.asList(nums[i], nums[j], nums[k]));
            }
        }
    }
    return result;
}
  1. 貌似是三层循环，但每一轮指针j和k的移动次数加起来最多n-1次，因此该解法的整体时间复杂度是O（n²）。
  2. 最关键的是，该解法并没有使用额外的集合（排序是直接在输入数组上进行的），所以空间复杂度只有O（1）

3另一种三数之和

给你一个包含 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] 输出：[]

思路

这道题完全可以看成，第一道题目三数之和的特殊版本，也就是target=0的版本

换成while循环重写一遍，其实是一样的思路

 public static List<List<Integer>> threeSums(int[] nums) {
     Arrays.sort(nums);
     List<List<Integer>> result = new ArrayList<>();
     for (int i = 0; i < nums.length; i++) {
         if (i > 0 && nums[i] == nums[i - 1]) {//去重
             continue;
         }
         int start = i + 1, end = nums.length - 1;
         int need = -nums[i];
         while (start < end) {
             int sum = nums[start] + nums[end];
             if (sum > need) {
                 end--;
             } else if (sum < need) {
                 start++;
             } else {
                 result.add(Arrays.asList(nums[i], nums[start], nums[end]));
                 while (start < end && nums[start] == nums[start + 1]) {//去重
                     start++;
                 }
                 while (start < end && nums[end] == nums[end - 1]) {//去重
                     end--;
                 }
                 start++;
                 end--;
             }
         }
     }
     return result;
 }

4最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

思路

做了三数之和题目后看到此题目想到的还是用排序+双指针方式，试着把这个思路实现

用了差不多十分钟写的并没有通过，感觉思路还是不顺

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int result = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) {
            int nextSum = nums[i] + nums[j] + nums[k];
            while (j < k) {
                if (Math.abs((target - nextSum)) < Math.abs(target - result)) {
                    result = nextSum;
                }
                if (target - nextSum > 0) {
                    k--;
                }
            }
        }
    }
    return result;
}

查看下大鹏的题解，真是太漂亮了，思路清晰、逻辑缜密，环环相扣

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    //初始和
    int ans = nums[0] + nums[1] + nums[2];
    for(int i=0;i<nums.length;i++) {
        //双指针
        int start = i+1, end = nums.length - 1;
        while(start < end) {
            int sum = nums[start] + nums[end] + nums[i];
            if(Math.abs(target - sum) < Math.abs(target - ans))
                ans = sum;
             //如果大于目标值，需要左移
            if(sum > target)
                end--;
            //如果小于目标值，需要右移
            else if(sum < target)
                start++;
            else
                return ans;
        }
    }
    return ans;
}

相关文章