“This is the 34th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[topic address]

You are given an integer array nums and an integer x. At each operation, you should remove the leftmost or rightmost element of nums and subtract that element’s value from x. Note that the array needs to be modified for subsequent operations.

If x can be reduced to 0 exactly, return the minimum operand; Otherwise, -1 is returned.

Example 1:

Input: nums = [1,1,4,2,3], x = 5 output: 2 explanation: the best solution is to remove the last two elements and reduce x to 0.Copy the code

Example 2:

Input: nums = [5,6,7,8,9], x = 4 output: -1Copy the code

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10 output: 5 explanation: the best solution is to remove the last three elements and the first two elements (total 5 operations) and reduce x to 0.Copy the code

Tip:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104
  • 1 <= x <= 109

Recursively, time out

Their thinking

We can delete one element at a time on the edge of the array of integers, and subtract the response number from the target value. If the target value can be reduced to 0, return the minimum number of operations. Such a problem, we can think of the first way to solve the problem may be to use recursion:

  1. The recursive function passes in the remaining value and the current interval, initially passed intarget = x,l = 0,r = nums.length-1.
  2. Each time you subtract the element on the left or the element on the right, and change the correspondingtarget,l,r.
  3. The first exit condition for a recursive function istarget===0, indicating that an operation has been found to reduce the target value to0If the number of operations is smaller than the recorded number of minor operations, the minimum number of operations is updated.
  4. Another exit condition for recursive functions isL > r | | target < 0 | | the operating frequency is greater than or equal to the recorded minimum number of operationsAt this point, there’s no point in continuing. Exit the recursion.

Code implementation

var minOperations = function (nums, X) {/** * recursive function * @param {number[]} target Remaining value to be subtracted * @param {number} l starting subscript of the unoperated interval * @param {number} r Ending subscript of the unoperated interval * @return void */ function calc(target, l, r) { if (target === 0 && l - 0 + len - r - 1 < res) { res = l - 0 + len - r - 1 return } if (l > r || target < 0 || l - 0 + len - r - 1 >= res) { return } calc(target - nums[l], l + 1, r) calc(target - nums[r], l, Const len = nums.length const len = nums.length const len = nums.length Let res = len + 1 // call the recursive function calc(x, 0, len-1) // If the result is valid, return the result, otherwise return -1 res > len? -1 : res }Copy the code

However, the time complexity of the above algorithm is O(n²), which does not meet the requirements of this problem.

Reverse thinking, sliding Windows

Their thinking

Recursive problem solving timeout, at this time we change a way of thinking, since the subject request every time can only delete at the edge of the array elements, so the rest of the elements must be in the array of “middle”, which means that they must be continuous, then we should find a continuous subarray, one of the elements and the value is equal to the input of the array elements and values minus the target value.

Code implementation

var minOperations = function (nums, Const len = nums.length const len = nums.length let total = 0 for (let I = 0; i < len; If (total < x) return -1 if (total < x) return -1 if (total < x) return -1 If (total === x) return len // Initializes the array length +1, Let res = len + 1, l = 0, Sum = 0 // Calculates the difference between the sum of the integers in the array and the target value => the sum of the elements in the target interval const diff = total -x // While the index does not reach the end of the array (r < len) {sum += nums[r] While (sum > diff) {sum -= nums[l] l++} If (sum === diff) res = math. min(res, len-r + l-1) r++} // Return len > len? -1 : res }Copy the code

The above algorithm has a time complexity of O(n) and beats 90+% of users after submission.

So we’re done with 1658 minus the minimum operand to reduce x to 0

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻