Hello Everyone, Recently in one of my interview Rounds ,I got asked this question, I just wanted to know is there any optimal way to do this ? in less than 0(nlogn) or 0(n) Complexity
Given an array of Integers(positive and negative) and Target Element K ,you have to find minimum absolute difference between target element and subarray summ. Also there are going to be q queries where each time you will have different K
do perfix sum, enumeration "l", Use multiset.lower_bound to find r
O(n log n)
But there are q queries each time you will have different K so question gets more complex
then it's 3-SUM, there's no any fast solution better then O(n^(2-eps)).
Auto comment: topic has been updated by B.i.b.e.r (previous revision, new revision, compare).