題目
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:
1Input: nums = [1,7,3,6,5,6]
2Output: 3
3Explanation:
4The pivot index is 3.
5Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
6Right sum = nums[4] + nums[5] = 5 + 6 = 11
Example 2:
1Input: nums = [1,2,3]
2Output: -1
3Explanation:
4There is no index that satisfies the conditions in the problem statement.
Example 3:
1Input: nums = [2,1,-1]
2Output: 0
3Explanation:
4The pivot index is 0.
5Left sum = 0 (no elements to the left of index 0)
6Right sum = nums[1] + nums[2] = 1 + -1 = 0
Constraints:
- 1 <= nums.length <= 104
- -1000 <= nums[i] <= 1000
我的思路
現在要從 Array 找 pivot , 就代表有個 index i 左邊所有數字的總和要等於右邊數字的總和。
用數學表示就會是 leftSum + rightSum + pivot = TotalSum
因為我們要找 leftSum = rightSum
所以 leftSum + rightSum + pivot = TotalSum
=> leftSum + leftSum + pivot = TotalSum
=> 2 * leftSum = TotalSum - pivot
=> leftSum = (TotalSum - privot) / 2
我們先 loop 一遍 Array 求出 totalSum
接著在 loop 第二次 Array 由左到右，用一個 Varaible leftSum 去計算到 index i 為止左邊累加的總數 ，所以根據剛剛得到的公式，如果 totalSum 減去當下 index i 的值並除二如果等於 leftSum 就代表這個 index 就是 provit。
如果 loop 完一遍了就代表找不到 provit，那就返回 -1
程式碼
1class Solution {
2 public int pivotIndex(int[] nums) {
3 int totalSum = 0;
4 for(int num : nums) {
5 totalSum += num;
6 }
7
8 //如果用 int，除2時會導致小數點無條件被捨去而成誤判
9 float leftSum = 0;
10 for(int i = 0; i < nums.length; i++) {
11 if (leftSum == ((float)(totalSum - nums[i]))/2 ) {
12 return i;
13 }
14 leftSum += nums[i];
15 }
16 return -1;
17 }
18}
評論