[LeetCode] 724. Find Pivot Index(Java)

Find Pivot Index - LeetCode

📚 문제

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

📝 문제 해결

좌/우 배열값의 합이 일치하는 pivot 인덱스를 찾는 문제로 전체 값의 합을 구한 다음 반복문을 돌면서 총합에서 좌측 배열의 값들을 빼다가 좌/우 배열값의 합이 같아지면 반복문을 종료하고 해당 인덱스를 반환해주면 된다.

요소 개수만큼 반복하므로 시간복잡도는 O(n)이 소요된다.

 

💻 코드

class Solution {
    public int pivotIndex(int[] nums) {
        int total = Arrays.stream(nums).sum();
        int leftSum = 0;

        for(int i=0; i<nums.length; i++){
            int rightSum = total - nums[i] - leftSum;

            if(leftSum == rightSum){
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
}