Problem
Given an array of integers nums, write a method that returns the "pivot" index of this array.
We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.
If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.
Example 1:
Input:
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.
Example 2:
Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Note:
The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].
class Solution { public int pivotIndex(int[] nums) { if (nums == null || nums.length < 3) return -1; int n = nums.length; int[] dp = new int[n]; int[] pd = new int[n]; dp[0] = nums[0]; pd[n-1] = nums[n-1]; for (int i = 1; i < n; i++) { dp[i] = dp[i-1]+nums[i]; } for (int i = n-2; i >= 0; i--) { pd[i] = pd[i+1]+nums[i]; } if (pd[1] == 0) return 0; for (int i = 1; i < n-1; i++) { if (dp[i-1] == pd[i+1]) return i; } if (dp[n-2] == 0) return n-1; return -1; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/72388.html
摘要:左邊的元素和為,剛好等于右邊的元素和。在第二趟遍歷中,檢查當(dāng)前元素左邊所有元素的加和,是否等于減去當(dāng)前元素的值,如果滿足,則當(dāng)前點為樞紐點,返回當(dāng)前元素的位置。 題目詳情 Given an array of integers nums, write a method that returns the pivot index of this array.We define the piv...
摘要:前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
摘要:在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目,語言 JavaScript。 在線網(wǎng)站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號: showImg(htt...
摘要:如果沒復(fù)雜度的要求,先也可以,再交叉放入數(shù)字也可以。交叉的時候注意是按照,降序的。 Wiggle Sort 題目鏈接:https://leetcode.com/problems... 這道題允許等號,相對簡單,有兩種方法:1. sort然后交換奇數(shù)位和它下一位的元素,2. 不滿足條件的時候直接交換 可以用遞推來說明一下這么做的正確性: 假設(shè)到第i位之前都滿足題目要求的關(guān)系 現(xiàn)在比較...
摘要:題目例子我的解法其他解法求最大值然后求二分法查找 1 題目 Lets call an array A a mountain if the following properties hold: A.length >= 3There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[...
閱讀 1125·2021-11-24 10:21
閱讀 2561·2021-11-19 11:35
閱讀 1662·2019-08-30 15:55
閱讀 1293·2019-08-30 15:54
閱讀 1192·2019-08-30 15:53
閱讀 3498·2019-08-29 17:21
閱讀 3308·2019-08-29 16:12
閱讀 3412·2019-08-29 15:23