删除 k 个连续元素使数组平衡

Problem

You are given an integer array nums of length \(n\) and an integer \(k\). Your task is to remove exactly \(k\) consecutive elements from nums so that the resulting array is balanced, which means the sum of values at even indices equals the sum of values at odd indices.

Return the smallest starting index of such a \(k\)-length consecutive elements to delete, or -1 if no valid removal exists.

Example 1:

Input: nums = [2, 1, 6, 4], k = 1

Output: 1

Explanation: Remove the element at index 1 (value 1), resulting in [2, 6, 4], where even indices (0, 2) sum is 2 + 4 = 6, odd indices (1) sum is 6

Example 2:

Input: nums = [1, 1, 1, 1, 1, 1], k = 2

Output: 0

Example 3:

Input: nums = [1, 2, 3], k = 1

Output: -1

Constraints:

• 1 <= k <= n <= \(10^5\)
• \(-10^9\) <= nums[i] <= \(10^9\)

Idea

Removing the window that starts at index \(s\) keeps the indices of the elements before it, but shifts every element after it left by \(k\). So when \(k\) is odd, the even and odd positions of the suffix swap; when \(k\) is even, they stay the same.

Slide a window of length \(k\) (the removed part) from left to right, and keep the sums of the elements before and after the window, each split by original index parity. Each step moves nums[s] into the before sums and takes nums[s + k] out of the after sums, so checking each start costs \(O(1)\). The first start whose even and odd totals are equal is the answer. The sums can reach \(10^{14}\), so use 64-bit integers.

Time complexity: \(O(n)\), Space complexity: \(O(1)\)

Pseudo Code

before = [0, 0];          // before[p]: sum of elements before the window at original index parity p
after = [0, 0];           // after[p]: sum of elements after the window at original index parity p
for (i = k; i < n; i++) {
    after[i % 2] += nums[i];
}
for (s = 0; s <= n - k; s++) {
    if (k % 2 == 0) {
        evenSum = before[0] + after[0];
        oddSum = before[1] + after[1];
    }
    else {                // the suffix shifts left by an odd amount, so its parity flips
        evenSum = before[0] + after[1];
        oddSum = before[1] + after[0];
    }
    if (evenSum == oddSum) {
        return s;
    }
    if (s + k < n) {      // slide the window one step right
        before[s % 2] += nums[s];
        after[(s + k) % 2] -= nums[s + k];
    }
}
return -1;