724. Find Pivot Index

출처 : https://leetcode.com/problems/find-pivot-index/

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

 

이 문제를 보았을 때, 어떻게 풀 수 있을까를 생각하다가 Index Pointer 방식이 생각났다.
Index pointer를 가지고, 왼쪽에서 부터 움직이면서 Left와 Right Sum을 계산해준다.
하지만 이 때, 항상 새로 계산하는 것은 낭비이니,
필요한 부분 : left += nums[Index_pointer - 1], right -=nums[Index_pinter + 1] 의 업데이트만 필요하다.

비교 후, 인덱스를 이동하며, left sum과 right sum을 업데이트한다면, 아래와 같은 솔루션이 나오게 된다. 

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int pivotIndex = 0;
        int left_sum = 0;
        int right_sum = 0;
        for (int i = 1; i < nums.size(); i++){
            right_sum += nums[i];
        }
        while(pivotIndex < nums.size()){
            if (left_sum == right_sum)
                return pivotIndex;
            left_sum += nums[pivotIndex];
            pivotIndex++;
            if (pivotIndex != nums.size())
                right_sum -= nums[pivotIndex];
        }
        return -1;
    }
};

하지만!!!, 이 방식은 좋지않다. 다음 Pivot Index에 대한 벡터 overflow를 막기 위해, if (pivotIndex != num.size())를 체크해주어야하기 때문이다. 

따라서, 우리는 불필요한 if (pivotIndex != num.size()) 을 없애야한다.

Left sum 은 pivot Index를 increment하면서 업데이트할 수 있는 부분이다.

하지만 Right sum 은?

Increment가 된 pivot Index에 접근하면서 업데이트되는 부분이다.

따라서, 우리는 이렇게 알고리즘 순서를 바꾸기로 한다.

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int pivotIndex = 0;
        int left_sum = 0;
        int right_sum = 0;
        for (int i = 0; i < nums.size(); i++){
            right_sum += nums[i];
        }
        while(pivotIndex < nums.size()){
            right_sum -= nums[pivotIndex];
            if (left_sum == right_sum)
                return pivotIndex;
            left_sum += nums[pivotIndex];
            pivotIndex++;
        }
        return -1;
    }
};

이 방식으로 나는 불필요한 If statement를 없앨 수 있게되었다.

 

Runtime 이 2.5배 가량 빨라졌다.