# 1755. Closest Subsequence Sum

```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 {

• ### No.016 3Sum Closest

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

• ### LeetCode Weekly Contest 26解题思路

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

• ### 01-复杂度2 Maximum Subsequence Sum (25分)

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

• ### 【PAT甲级】Maximum Subsequence Sum

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

• ### python编写PAT 1007 Max

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

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

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

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

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

• ### 【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...

• ### 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...

• ### Array - 16. 3Sum Closest

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

• ### PAT 1007

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

• ### 算法：Solutions for the Maximum Subsequence Sum Problem

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

• ### Leetcode 16 3Sum Closest

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

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

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

• ### PAT 1007 Maximum Subsequence Sum（最长子段和）

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