|
| 1 | +```text |
| 2 | +题目: |
| 3 | + 给定一个包括n个整数的数组nums和一个目标值target; |
| 4 | + 找出nums中的三个整数,使得它们的和与target最接近; |
| 5 | + 返回这三个数的和;假定每组输入只存在唯一答案; |
| 6 | + 示例: |
| 7 | + 输入: nums = [-1,2,1,-4], target = 1 |
| 8 | + 输出: 2 |
| 9 | + 解释: 与 target 最接近的和是 2 (-1 + 2 + 1 = 2) |
| 10 | + 提示: |
| 11 | + 3 <= nums.length <= 10^3 |
| 12 | + -10^3 <= nums[i] <= 10^3 |
| 13 | + -10^4 <= target <= 10^4 |
| 14 | +1.三重暴力循环: |
| 15 | + [1]思路: |
| 16 | + (1)求每次遍历到的三数之和与目标值的差值,一旦出现差值的绝对值更小的 |
| 17 | + 则保存差值并更新最终返回结果; |
| 18 | + [2]实现: |
| 19 | + class Solution { |
| 20 | + public int threeSumClosest(int[] nums, int target) { |
| 21 | + int minDiff = Integer.MAX_VALUE; |
| 22 | + int result = 0; |
| 23 | + for (int i = 0; i < nums.length-2; i++) { |
| 24 | + for (int j = i+1; j < nums.length-1; j++) { |
| 25 | + for (int k = j+1; k < nums.length; k++) { |
| 26 | + if(Math.abs(minDiff)>=Math.abs(nums[i]+nums[j]+nums[k]-target)){ |
| 27 | + minDiff = nums[i]+nums[j]+nums[k]-target; |
| 28 | + result = nums[i]+nums[j]+nums[k]; |
| 29 | + } |
| 30 | + } |
| 31 | + } |
| 32 | + } |
| 33 | + return result; |
| 34 | + } |
| 35 | + } |
| 36 | + [3]复杂度分析: |
| 37 | + (1)时间复杂度: O(N^3),其中N是数组长度 |
| 38 | + (2)空间复杂度: O(1) |
| 39 | +2.双指针: |
| 40 | + [1]思路: |
| 41 | + (1)利用双指针遍历将两层循环遍历降低到一层遍历; |
| 42 | + (2)更新结果变量的条件: 出现更小的差值的绝对值(此时需要确定好初始差值) |
| 43 | + (3)左指针右移的条件: 三数之和小于目标值; |
| 44 | + (4)右指针左移的条件: 三数之和大于目标值; |
| 45 | + (5)当三数之和等于目标值则直接返回三数之和; |
| 46 | + [2]实现: |
| 47 | + class Solution { |
| 48 | + public int threeSumClosest(int[] nums, int target) { |
| 49 | + int len = nums.length; |
| 50 | + // 先排序,降低后续处理的难度 |
| 51 | + Arrays.sort(nums); |
| 52 | + // 定义一个变量用来保存三个数之和与目标值的差的绝对值 |
| 53 | + int ans = nums[0] + nums[1] + nums[2]; |
| 54 | + for (int i = 0; i < len - 2; i++) { |
| 55 | + //定义左右指针 |
| 56 | + int left = i + 1; |
| 57 | + int right = len - 1; |
| 58 | + //双指针遍历 |
| 59 | + while (left < right) { |
| 60 | + int temp = nums[i] + nums[left] + nums[right]; |
| 61 | + // 当三数之和与目标值的差的绝对值比上一次的小时,更新三数之和 |
| 62 | + if (Math.abs(temp - target) < Math.abs(ans - target)) { |
| 63 | + ans = temp; |
| 64 | + } |
| 65 | + if (temp == target) { |
| 66 | + // 当三数之和等于目标值时,此时就是最接近,直接返回 |
| 67 | + return ans; |
| 68 | + } else if (temp > target) { |
| 69 | + // 当三数之和大于目标值,则需要右指针左移,探测更小的三数之和 |
| 70 | + right--; |
| 71 | + } else { |
| 72 | + // 当三数之和大于目标值,则需要左指针右移,探测更大的三数之和 |
| 73 | + left++; |
| 74 | + } |
| 75 | + } |
| 76 | + } |
| 77 | + return ans; |
| 78 | + } |
| 79 | + } |
| 80 | + [3]复杂度分析: |
| 81 | + (1)时间复杂度: O(N^2),其中N是数组长度 |
| 82 | + (2)空间复杂度: O(1) |
| 83 | +``` |
0 commit comments