<Hard> Count of Range Sum (LeetCode : C#)

https://leetcode.com/problems/count-of-range-sum/

📕 문제 설명

정수 배열 nums와 upper, lower 정수가 주어질 때 [lower, upper] 범위에 있는 range sum 반환하기 (inclusive)

range sum은 nums 배열의 element들의 range 만큼의 합 조합으로 해당 range안에 들어올 수 있는 값들을 의미한다.

• Input
  정수 배열 nums, lower, upper
• Output
  [lower, upper] 구간의 range sum element 개수 반환하기

예제

[-2, 5, -1] => -2, 5, -1, (-2 + 5), (5 - 1), (-2 + 5 - 1)
-2~2 구간에 들어오는 값 : -2, -1, 2

풀이

public class Solution {
    int lower, upper;
    long[] preSum;
    long[] temp;
    int count = 0;
    public int CountRangeSum(int[] nums, int lower, int upper) {
        this.lower = lower;
        this.upper = upper;
        preSum = new long[nums.Length + 1];
        temp = new long[nums.Length + 1];
        for (int i = 0; i < nums.Length; i++) preSum[i + 1] = preSum[i] + nums[i]; // 이전 값들 합 + 현재값 
        Sort(preSum, 0, preSum.Length - 1);
        return count;
    }
    public void Sort(long[] nums, int left, int right)
    {
        if (left >= right) return;
        int mid = (left + right) / 2;
        Sort(nums, left, mid); // 왼쪽
        Sort(nums, mid + 1, right); // 오른쪽
        Merge(nums, left, mid, right);
    }
    public void Merge(long[] nums, int left, int mid, int right)
    {
        for (int i = left; i <= right; i++) temp[i] = nums[i];
 
        int start = mid + 1;
        int end = mid + 1;
        for (int i = left; i <= mid; i++)
        {
            while (start <= right && nums[start] - nums[i] < lower) start++; // RangeSum(i, start)가 lower보다 작을때까지 이동 (즉, lower 이상인 경우로 index 설정) 
            while (end <= right && nums[end] - nums[i] <= upper) end++; // RangeSum(i, end)가 upper보다 작을때까지 이동 (upper 직전까지로 index 설정)
                
            count += end - start; // 구간안의 값들 count
        }

        int m = left;
        int n = mid + 1;
        for (int i = left; i <= right; i++) // nums (merged) 배열 업데이트 
        {
            if (m == mid + 1) nums[i] = temp[n++]; // 왼쪽 끝까지 본 케이스 -> 오른쪽 담기 
            else if (n == right + 1) nums[i] = temp[m++]; // 오른쪽 끝까지 간 케이스 -> 왼쪽 담기
            else if (temp[m] > temp[n]) nums[i] = temp[n++]; // 오른쪽 더 작으니 커서 하나 옮기고, 옮기기 전 값 넣기
            else nums[i] = temp[m++]; // 왼쪽 더 작으니 왼쪽 커서 옮기고, 옮기기 전 값 넣기 
        }
    }
}

결과