前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 1755. 最接近目标值的子序列和(状态枚举 + 双指针)

LeetCode 1755. 最接近目标值的子序列和(状态枚举 + 双指针)

作者头像
Michael阿明
发布2021-09-07 11:09:04
6940
发布2021-09-07 11:09:04
举报
文章被收录于专栏:Michael阿明学习之路

文章目录

1. 题目

给你一个整数数组 nums 和一个目标值 goal 。

你需要从 nums 中选出一个子序列,使子序列元素总和最接近 goal 。 也就是说,如果子序列元素和为 sum ,你需要 最小化绝对差 abs(sum - goal)

返回 abs(sum - goal) 可能的 最小值

注意,数组的子序列是通过移除原始数组中的某些元素(可能全部或无)而形成的数组。

代码语言:javascript
复制
示例 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. 解题

  • 直接枚举,时间复杂度 2 40 ≈ 1 0 12 2^{40} \approx 10^{12} 240≈1012,肯定超时
  • 分治枚举,取出一半来枚举 2 20 ≈ 1 0 6 2^{20} \approx 10^6 220≈106,然后对两半边的状态排序,双指针求解
代码语言:javascript
复制
class Solution {
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        int n = nums.size();
        vector<int> 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++;
            else
                break;
        }
        return diff;
    }
    void getsum(vector<int>& nums, int l, int r, vector<int>& arr)
    {
        int n = r-l;
        arr.resize(1<<n);
        for(int i = 0; i < (1<<n); i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i & (1 << j))
                    continue;// i 状态 包含 j 数字
                arr[i+(1<<j)] = arr[i] + nums[l+j];
            }
        }
        sort(arr.begin(), arr.end());
    }
};

1180 ms 29.2 MB C++


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/02/09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档