专栏首页算法修养1755. Closest Subsequence Sum

1755. Closest Subsequence Sum

题目

题意:从一个数组找出一个子集,使得子集的和给定的目标最相近。

题解:数组的长度为40,找出全部子集一共有240种可能性,如果把一个数组平均分成两部分,分别算出两部分的所有子集和,每部分有220种可能, 然后再二分查找答案。

遇到这种在数组里找所有子集和,

class Solution {
public:
   map<int, int> m;
int sum[1000005];
int sum2[1000005];
int p;
void fun(int n, int i, int s,vector<int>& nums, int* sum)
{
	if (m[s] == 0)
	{
		m[s] = 1;
		sum[p++] = s;
	}
	
	for (int j = i + 1; j < n; j++)
	{
		fun(n, j, s+nums[j], nums, sum);
	}
}
    
    int minAbsDifference(vector<int>& nums, int goal)
{
	int ans = INT_MAX;
	int n = nums.size()/2;
	p = 0;
	for (int i = 0; i < n; i++)
	{
		fun(n, i, nums[i], nums, sum);
	}
	int p1 = p;
	m.clear();
	for (int i = 0; i < p1; i++)
	{
		ans = min(ans, abs(sum[i] - goal));
	}
	p = 0;
	for (int i = n; i < nums.size(); i++)
	{
		fun(nums.size(), i, nums[i],nums, sum2);
	}
	for (int i = 0; i < p; i++)
	{
		ans = min(ans, abs(sum2[i] - goal));
	}

	sort(sum, sum + p1);
	
	// 1 2 5 6
	for (int i = 0; i < p; i++)
	{
		int x = sum2[i];

		int l = 0;
		int r = p1;

		while (l <= r)
		{
			int mid = (l + r) / 2;
			ans = min(ans, abs(sum[mid] + x - goal));
			if (sum[mid] + x > goal)
			{
				r = mid - 1;
			}
			else if (sum[mid] + x < goal)
			{
				l = mid + 1;
			}
			else
			{
				return 0;
			}
		}
	}
	return ans;
}


};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1007 Maximum Subsequence Sum

    }. A continuous subsequence is defined to be {

    KevinBruce
  • No.016 3Sum Closest

    16. 3Sum Closest Total Accepted: 86565 Total Submissions: 291260 Difficulty: Med...

    mukekeheart
  • LeetCode Weekly Contest 26解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 01-复杂度2 Maximum Subsequence Sum (25分)

    Given a sequence of KK integers { N_1N ​1 ​​ , N_2N ​2 ​​ , …, N_KN ​K...

    AI那点小事
  • 【PAT甲级】Maximum Subsequence Sum

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • python编写PAT 1007 Max

    Given a sequence of K integers { N​1, N2, ..., N​K}. A continuous subsequence is...

    py3study
  • leetcode: 16. 3Sum Closest

    JNingWei
  • 2018-12-15 LintCode LeeCode刷题指南 part1

    从开始这个Github已经有将近两年时间, 很高兴这个repo可以帮到有需要的人. 我一直认为, 知识本身是无价的, 因此每逢闲暇, 我就会来维护这个repo,...

    Albert陈凯
  • leetcode 16 3Sum Closest

    @坤的
  • PAT 1007 Maximum Subsequence Sum (25分) 最大连续子序列和

    Given a sequence of K integers { N​1​​ , N​2​​ , ..., N​K​​ }. A continuous subs...

    vivi
  • 【leetcode】3Sum Closest

    Given an array S of n integers, find three integers in S such that the sum is cl...

    阳光岛主
  • LeetCode 0016 - 3Sum Closest

    Given an array S of n integers, find three integers in S such that the sum is cl...

    Reck Zhang
  • Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)C. The Phone Number

    Mrs. Smith is trying to contact her husband, John Smith, but she forgot the secr...

    glm233
  • Array - 16. 3Sum Closest

    Given an array nums of n integers and an integer target, find three integers in ...

    用户5705150
  • PAT 1007

    Given a sequence of K integers { N1, N2, ..., NK }. A continuous subsequence is...

    week
  • 算法:Solutions for the Maximum Subsequence Sum Problem

    The maximum subarray problem is the task of finding the contiguous subarray wit...

    s1mba
  • Leetcode 16 3Sum Closest

    Given an array S of n integers, find three integers in S such that the sum is c...

    triplebee
  • 【leetcode刷题】T4-3Sum Closest

    今天分享leetcode第4篇文章,也是leetcode第16题—3Sum Closest,地址是:https://leetcode.com/problems/...

    木又AI帮
  • PAT 1007 Maximum Subsequence Sum(最长子段和)

    1007. Maximum Subsequence Sum (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 1...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券