[LeetCode] Find Pivot Index

 

 

목차

 

문제

• pivot 기준 왼쪽의 합과 오른쪽 합이 같아지는 pivot의 인덱스를 구하는 문제입니다.
• 예시

  • 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

• 제약조건
  • 1 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000

문제 풀이

풀이 1 : Prefix Sum

• 풀이
  • 왼쪽 오른쪽 합에 해당 인덱스 값을 더하고 빼주면서 같아지는 부분의 인덱스를 리턴하면 됩니다.
• 코드

  • class Solution:
    
        def pivotIndex(self, nums: List[int]) -> int:
            left_sum, right_sum = 0, sum(nums)
            for i in range(len(nums)):
                right_sum-=nums[i]
                if left_sum==right_sum:
                    return i
                left_sum+=nums[i]
    
            return -1

• 시간복잡도
  • O(N)

알게 된 내용

• 누적합과 구간합
  • 특정 배열에서 특정 구간의 합을 구할 때는 누적합을 미리 구해두고, 누적 합끼리 빼서 구간합을 구하는 방법이 있습니다.
  • 예를 들어 1 2 3 4 5 6 배열이 있을 때 이때 누적합은 1 3 6 10 15 21 이 됩니다. 여기서 만약 3~5번째 값의 합을 구하라고 한다면 누적합[5]-누적합[3-1] = 12의 방법을 적용할 수 있습니다.

출처

• https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3230/