摘要:这个题和的做法基本一样,只要在循环内计算和最接近的和,并赋值更新返回值即可。
Problem
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.
NoticeYou may assume that each input would have exactly one solution.
ExampleFor example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
ChallengeO(n^2) time, O(1) extra space
Note这个题和3Sum的做法基本一样,只要在循环内计算和target最接近的和sum,并赋值更新返回值min即可。
Solutionpublic class Solution { public int threeSumClosest(int[] A ,int target) { int min = Integer.MAX_VALUE - target; if (A.length < 3) return -1; Arrays.sort(A); for (int i = 0; i <= A.length-3; i++) { int left = i+1, right = A.length-1; while (left < right) { int sum = A[i]+A[left]+A[right]; if (sum == target) return sum; else if (sum < target) left++; else right--; min = Math.abs(min-target) < Math.abs(sum-target) ? min : sum; } } return min; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65952.html
摘要:双指针法的解法。然后用和夹逼找到使三数和为零的三数数列,放入结果数组。对于这三个数,如果循环的下一个数值和当前数值相等,就跳过以避免中有相同的解。 Problem Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplet...
摘要:找符合条件的总数。双指针区间考虑边界,长度,为空,等。之后的范围用双指针和表示。若三个指针的数字之和为,加入结果数组。不要求,所以不用判断了。同理,头部两个指针向后推移,后面建立左右指针夹逼,找到四指针和为目标值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...
摘要:返回这三个值的和。思路一三指针这里的思路和是一样的,就是用三个指针获得三个值并计算他们的和。 题外话 鉴于这一题的核心思路和leetcode15的思路相同,可以先写一下15题并参考一下我之前的一篇博客 题目要求 Given an array S of n integers, find three integers in S such that the sum is closest to...
摘要:题目详情给定一个整数数组,我们需要找出数组中三个元素的加和,使这个加和最接近于输入的数值。返回这个最接近的加和。找后两个元素的时候,使用左右指针从两端查找。 题目详情 Given an array S of n integers, find three integers in S such that the sum is closest to a given number, targe...
摘要:为了避免得到重复结果,我们不仅要跳过重复元素,而且要保证找的范围要是在我们最先选定的那个数之后的。而计算则同样是先选一个数,然后再剩下的数中计算。 2Sum 在分析多数和之前,请先看Two Sum的详解 3Sum 请参阅:https://yanjia.me/zh/2019/01/... 双指针法 复杂度 时间 O(N^2) 空间 O(1) 思路 3Sum其实可以转化成一个2Sum的题,...
阅读 813·2021-11-15 11:37
阅读 3566·2021-11-11 16:55
阅读 3247·2021-11-11 11:01
阅读 972·2019-08-30 15:43
阅读 2710·2019-08-30 14:12
阅读 650·2019-08-30 12:58
阅读 3343·2019-08-29 15:19
阅读 1953·2019-08-29 13:59