724. Find Pivot Index (使用 C 語言 解題)

724. Find Pivot Index

Solved

Easy

Topics

Companies

Hint

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

 

Constraints:

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

 

Note: This question is the same as 1991: https://leetcode.com/problems/find-the-middle-index-in-array/

google 翻譯：

給定一個整數數組 nums，計算該數組的主元索引。
樞軸索引是嚴格位於索引左側的所有數字總和等於嚴格位於索引右側的所有數字總和的索引。

如果索引位於陣列的左邊緣，則左和為 0，因為左側沒有元素。這也適用於數組的右邊緣。
傳回最左邊的樞軸索引。如果不存在這樣的索引，則傳回-1。

想法一：

宣告兩個陣列，一個陣列存放從左邊開始往右加的總值，
另一個陣列存放從右邊開始往左加的總值。
再用一個迴圈判斷這兩個陣列，在相對的位置是否相同

寫法一：

int pivotIndex(int* nums, int numsSize) {
    int *left = malloc(sizeof(int) * (numsSize+2));
    int *right = malloc(sizeof(int) * (numsSize+2));
    int k, ret = -1;

    // 從右邊加到左邊的陣列，最右邊放 0
    k = 0;
    right[numsSize] = k;
    for(int i=numsSize-1; i >= 0; i--) {
        k += nums[i];
        right[i] = k;
    }

    // 從左邊加到右邊的陣列，最左邊放 0
    k = 0;
    left[0] = k;
    for(int i=0; i < numsSize; i++) {
        k += nums[i];
        left[i+1] = k;
    }

    // 判斷前兩個陣列在相對位置的值是否相同
    k = -INT_MAX; // 用來判斷相同的值是否是陣列中的最大，但在這裡沒必要
    for(int i=1; i<numsSize+1; i++) {
        if(left[i-1] == right[i] /*&& k < left[i-1]*/) {
//            k = left[i-1];
            ret = i-1;
            break;
        }
    }

    return ret;
}

結果一：

結果還行，再來看看可以怎麼改進...

想法二：

先把所有的值加總起來sumRight，當作是從右加到左的陣列
再跑一次迴圈，把sumRight減掉目前的數值，即是從右加到左陣列的相對位置值。
其中有另一個變數sumLeft當作是從左加到右的陣列，比較sumLeft與sumRight，
相同代表有解。

寫法二：

int pivotIndex(int* nums, int numsSize) {
    int sumLeft = 0, sumRight = 0;

    // 從右加到左的陣列 (所以第一個值是總加總)
    for(int i=0; i<numsSize; i++) {
        sumRight += nums[i];
    }

    for(int i=0; i<numsSize; i++) {
        sumRight -= nums[i]; // 從右加到左的陣列
        if(sumLeft == sumRight) { // 相同代表有解
            return i;
        }
        sumLeft += nums[i]; // 從左加到右的陣列
    }
    return -1;
}

結果二：

結果還不錯哦~