Skip to content

Commit 4227dcd

Browse files
authored
Create Readme.md
1 parent 1bfff4c commit 4227dcd

1 file changed

Lines changed: 7 additions & 0 deletions

File tree

  • Hash/1658.Minimum-Operations-to-Reduce-X-to-Zero
Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
### 1658.Minimum-Operations-to-Reduce-X-to-Zero
2+
3+
本题的题意是:在nums数组里找a个元素的前缀和,与b个元素的后缀和,使得他们的sum是x,问如果能找到的话,a+b最少是多少?
4+
5+
比较直观的算法就是:从右往左遍历b的数目,给定了b,我们就要确定多少个元素的前缀和presum[a],恰好等于x-sufsum[b]。显然,我们可以提前遍历数组来构建所有presum[i]->i的hash表。利用这个hash表就能用o(1)时间快速得到指定前缀和所对应的位置。只要这个位置i小于b,那么i和b就是一对合法的解。
6+
7+
最终答案是遍历所有的b,找到i+(n-b)的最小值。

0 commit comments

Comments
 (0)