문제 링크

https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/

문제 풀이

맨왼쪽이나 맨 오른쪽의 숫자를 뽑은 누적합이 x 가 되는 최소 동작 횟수를 구하는 문제이다. (불가능하면 -1을 return)

문제 그대로 구현을 하는데 애를 먹었다. 결국 문제에서 제공하는 Hide Hint 를 봤는데 오히려 최대 길이의 subarray를 구하라는 역발상을 이용하는 문제였다. 힌트에 나온대로 subarray를 구하기 위해 투포인터를 사용하여 total-x 를 만족하는 subarray의 최대 길이를 구한 후 nums.length 에서 뺀 값을 return 하였다.

나의 코드

var minOperations = function (nums, x) {
  const total = nums.reduce((acm, cur) => acm + cur, 0);
  if (x === total) return nums.length;
  let answer = -1;
  let sum = 0;
  let lo = 0;
  let len = 0;
  for (let hi = 0; hi < nums.length; ++hi) {
    sum += nums[hi];
    ++len;
    if (sum === total - x) answer = Math.max(answer, len);
    while (sum > total - x) {
      sum -= nums[lo++];
      --len;
      if (sum === total - x) answer = Math.max(answer, len);
    }
  }
  return answer === -1 ? -1 : nums.length - answer;
};