Re: [閒聊] 每日LeetCode

[sustainer123 (caster)]

724. Find Pivot Index
給定一個整數陣列 nums ，撰寫一函式回傳陣列的「樞紐」之索引值（從 0 開始數）。

我們定義樞紐為滿足陣列上的某位置之數字，其左邊的所有數字之和等於其右邊所有數字
之和。

如果樞紐不存在，我們應回傳 -1 。如果有多個樞紐，則回傳最左邊的樞紐之索引值。

限制：
nums 的長度位於 [0, 10000] 範圍之中。
nums[i] 之值位於 [-1000, 1000] 範圍之中。

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

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


思路:
先算出nums的全部總和,後面區分num[0]與其他兩種情況,num[0]時,左邊總和為0,
故右邊總和為全部總和-num[0];
其他狀況時,左邊總和就是num[1]+...+num[i-1],迴圈從num[1]加上去,
右邊總和就是全部總和-左邊總和-num[i]
最後判斷左邊總和是否等於右邊總和,如相等,則樞紐=i並回傳樞紐值
如不相等,則繼續進行迴圈。
如若無樞紐,則回傳-1

C Code：
------------------

int pivotIndex(int* nums, int numsSize){
    int pivotindex;
    int leftsum=0;
    int rightsum=0;
    int totalsum=0;
    for(int i=0; i<numsSize; i++){
        totalsum += nums[i];
    }
    for(int i=0; i<numsSize; i++){
       if(i == 0){
           rightsum = totalsum - nums[i];
       }else{
           leftsum += nums[i-1];
           rightsum = totalsum - leftsum - nums[i];
       }
       if(leftsum == rightsum){
           pivotindex = i;
           return pivotindex;
        }
    }
    return -1;
}

------------------

補記:這題原本寫法會超時

後來修掉兩層迴圈才過關

今天學到時間複雜度的觀念 賺
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.119.103 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672063069.A.C14.html
推 SecondRun: 大師
→ sustainer123: 我是剛踏上刷題之路的廢物QQ
推 DDFox: 大師
※ 編輯: sustainer123 (223.137.14.32 臺灣), 12/26/2022 22:07:42
推 pandix: 刷題幫讚讚
推 AyuniD: 其實一開始的 rightsum 就是 totalsum - nums[0]，後面的
→ AyuniD: leftsum 跟 rightsum 也不用一直重算，就把現在處理到的
→ AyuniD: 加或減進去就好了。
→ AyuniD: 另外變數名稱可以用 camelCase 或 snake_case，一點小習慣
→ AyuniD: 可以增加可讀性，加油！