重庆便宜网站建设,济南网站建设公司-远大云.,邯郸网站建设提供商,石大远程网页设计与网站建设答案文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums 和一个目标值 goal 。
你需要从 nums 中选出一个子序列#xff0c;使子序列元素总和最接近 goal 。 也就是说#xff0c;如果子序列元素和为 sum #xff0c;你需要 最小化绝对差 abs(sum - goal) 。
返回 abs(sum …
文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums 和一个目标值 goal 。
你需要从 nums 中选出一个子序列使子序列元素总和最接近 goal 。 也就是说如果子序列元素和为 sum 你需要 最小化绝对差 abs(sum - goal) 。
返回 abs(sum - goal) 可能的 最小值 。
注意数组的子序列是通过移除原始数组中的某些元素可能全部或无而形成的数组。
示例 1
输入nums [5,-7,3,5], goal 6
输出0
解释选择整个数组作为选出的子序列元素和为 6 。
子序列和与目标值相等所以绝对差为 0 。示例 2
输入nums [7,-9,15,-2], goal -5
输出1
解释选出子序列 [7,-9,-2] 元素和为 -4 。
绝对差为 abs(-4 - (-5)) abs(1) 1 是可能的最小值。示例 3
输入nums [1,2,3], goal -7
输出7提示
1 nums.length 40
-10^7 nums[i] 10^7
-10^9 goal 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/closest-subsequence-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
直接枚举时间复杂度 240≈10122^{40} \approx 10^{12}240≈1012肯定超时分治枚举取出一半来枚举 220≈1062^{20} \approx 10^6220≈106然后对两半边的状态排序双指针求解
class Solution {
public:int minAbsDifference(vectorint nums, int goal) {int n nums.size();vectorint arr1, arr2;getsum(nums, 0, n/2, arr1);getsum(nums, n/2, n, arr2);int i 0, j arr2.size()-1, n1 arr1.size();int diff INT_MAX, sum;while(i n1 j 0){sum arr1[i] arr2[j];diff min(diff, abs(sum-goal));if(sum goal)j--;else if(sum goal)i;elsebreak;}return diff;}void getsum(vectorint nums, int l, int r, vectorint arr){int n r-l;arr.resize(1n);for(int i 0; i (1n); i){for(int j 0; j n; j){if(i (1 j))continue;// i 状态 包含 j 数字arr[i(1j)] arr[i] nums[lj];}}sort(arr.begin(), arr.end());}
};1180 ms 29.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
