Re: [闲聊] 每日LeetCode

楼主: pandix (面包屌)   2022-10-08 13:02:09
※ 引述《Rushia (みけねこ的鼻屎)》之铭言:
: 16. 3Sum Closest
: 给定一个长度大于3的整数阵列和一个数字target,求出最接近target的任意三数之和,
: 假定测资只存在恰好一解。
: Example 1:
: Input: nums = [-1,2,1,-4], target = 1
: Output: 2
: Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
: 法二 双指标
: 思路:
: 1.题目要求与target最接近的sum,所以:
: A + B + C = sum ==> 趋近于target
: 我们可以把他移项:
: B + C = 趋近于target - A
: 该问题就会退化为在阵列里搜寻最接近 target 的 B + C
: 2.先把整个阵列排序,这样可以快速的取值且排除掉使用过的组合。
: 3.遍历阵列,把nums[i]当作第一个加数A,并从右取最大和最小值当B和C。
: sum = A + B + C
: 4.依据状况移动指标,分两case:
: 若sum > target 表示我们要再拿更小 right
作者: Rushia (みけねこ的鼻屎)   2022-10-08 13:09:00
应该说如果存在更小的绝对值就会逼近不存在还是会乖乖的遍历跑完 因为没提早跳出主要是把n^2压成n
楼主: pandix (面包屌)   2022-10-08 13:23:00
对 只是说单用绝对值没办法解释正确性

Links booklink

Contact Us: admin [ a t ] ucptt.com