Leetcode算法Java全解答--16. 最接近的三数之和

谁借莪１个温暖的怀抱￠ 2022-04-17 01:15 102阅读 0赞

# Leetcode算法Java全解答–16. 最接近的三数之和 #

### 文章目录 ###

*  Leetcode算法Java全解答--16. 最接近的三数之和
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *   *  暴力破解
             *  滑动列表
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

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

示例：

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
    与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

## 想法 ##

1.  暴力破解法：  
    循环三轮
2.  使用前面三数之和的逻辑
    
    1.  排序数组
    2.  以第一个数为起点，后面2数进行滑动列表操作

## 结果 ##

超过99%的测试案

时间复杂度：n2

空间复杂度：1

## 总结 ##

## 代码 ##

### 我的答案 ###

#### 暴力破解 ####

/**
         * 暴力破解
         * 超过5%的测试案例
         * 时间复杂度：n3
         * 空间复杂度：1
         *
         * @param nums   数组
         * @param target 目标值
         * @return 结果
         */
        public int threeSumClosestByBrute(int[] nums, int target) {
            if (nums == null || nums.length < 3) {
                return 0;
            }
    
            int comp = Integer.MAX_VALUE;
            int result = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    for (int k = j + 1; k < nums.length; k++) {
                        int tmp = nums[i] + nums[j] + nums[k];
                        if (comp > Math.abs(tmp - target)) {
                            comp = Math.abs(tmp - target);
                            result = tmp;
                        }
                    }
                }
            }
    
            return result;
        }

#### 滑动列表 ####

/**
         *      时间复杂度：n2
         *      空间复杂度：1
         * 代码执行过程：
         *
         * 总结：
         *
         * ***********************************/
        public int threeSumClosest(int[] nums, int target) {
    
            if (nums == null || nums.length < 3) {
                return 0;
            }
            Arrays.sort(nums);
    
            int comp = Integer.MAX_VALUE;
            int result = Integer.MAX_VALUE;
    
            for (int i = 0; i < nums.length; i++) {
                // 如果和之前那个数据相同，则会是重复事件
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
    
                int leftIndex = i + 1;
                int rightIndex = nums.length - 1;
    
                // 滑动列表
                while (leftIndex < rightIndex) {
                    int tmp = nums[leftIndex] + nums[rightIndex] + nums[i];
                    if (comp > Math.abs(tmp - target)) {
                        comp = Math.abs(tmp - target);
                        result = tmp;
                    }
    
                    if (tmp > target) {
                        rightIndex--;
                    } else if (tmp < target) {
                        leftIndex++;
                    } else {
                        // 差值为0，最爽了，直接返回
                        return tmp;
                    }
                }
            }
            return result;
        }

### 大佬们的答案 ###

/**************************************
         * 比我好的答案 better
         * ***********************************/
        public int better(int[] nums, int target) {
    
            int result = nums[0] + nums[1] + nums[2];
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 2; i++) {
                int start = i + 1, end = nums.length - 1;
    
                while (start < end) {
                    int tmpSum = nums[i] + nums[start] + nums[end];
                    if (Math.abs(tmpSum - target) < Math.abs(result - target)) {
                        result = tmpSum;
                    }
                    if (tmpSum < target) {
                        start++;
                    } else if (tmpSum > target) {
                        end--;
                    } else {
                        return result;
                    }
    
                }
            }
            return result;
        }

### 测试用例 ###

@Test
        public void test016() {
            // 创建测试案例
            int[] arr1 = new int[] { -1, 2, 1, -4 };
            int target1 = 1;
    
            // 测试案例期望值
            int expResult1 = 2;
    
            // 执行方法
            Solution016 solution016 = new Solution016();
            int result1 = solution016.threeSumClosest(arr1,target1);
    
            // 判断期望值与实际值
            Assert.assertEquals(expResult1, result1);
    
        }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan