解法1：初始解法
思路： 长度为1的数组，中心索引一定是它本身的那个唯一元素，左右两边的和都为0。
长度为2的数组，除非两个元素都为0 那么这样才存在中心索引，且选最左边的0
长度大于等于2的数组：我们现在讨论普遍的情况，令索引 i 左边的值相加和索引右边的值相加的和作比较，相等的话直接返回i。太慢了！！！
public static int pivotIndex1(int[] nums) {
if(nums.length == 1) return 0;
if(nums.length == 2 && nums[0] == 0 && nums[nums.length-1] == 0){
return 0;
}
if(nums.length >= 2){
for(int i=0;i < nums.length;i++){
int sum1 = 0;
int sum2 = 0;
for(int t = 0; t < i;t++){
sum1 += nums[t];
}
for(int s = nums.length-1;s > i;s--){
sum2 += nums[s];
}
if(sum1 == sum2){
return i;
}
}
}
return -1;
}
//执行用时：519 ms, 在所有 Java 提交中击败了5.04%的用户
//内存消耗：38.8 MB, 在所有 Java 提交中击败了82.22%的用户
解法2：
思路：利用前缀和进行解题
什么是前缀和？前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。
分析本题：这是一道前缀和的裸题
只需要用两个数组，前后处理两遍前缀和，再对两个前缀和数组的相同下标进行判别即可。
为了简化数组越界判断，我们通常会给前缀和数组多预留一位作为哨兵。这里由于要求数组前后 算上的前缀和。所以我们直接给数组多开两位即length = n+2
public int pivotIndex2(int[] nums) {
int n = nums.length;
int[] s1 = new int[n + 2], s2 = new int[n + 2];
//正着的前缀和数组，注意这里的i 是从1 与 n 开始的
for (int i = 1; i <= n; i++) s1[i] = s1[i - 1] + nums[i - 1];
//反着的前缀和数组
for (int i = n; i >= 1; i--) s2[i] = s2[i + 1] + nums[i - 1];
for (int i = 1; i <= n; i++) {
if (s1[i] == s2[i]) return i - 1;
}
return -1;
}
//执行用时: 2 ms
//内存消耗: 38.8 MB
解法3：
思路：转换思路解题，中心下标左右的元素相加之和相等，转换成——左边求和*2 + 中心索引值 = 总和；
public int pivotIndex(int[] nums) {
//求总和
int sum = 0;
for(int i = 0;i<nums.length;i++){
sum += nums[i];
}
//求索引左边的和
int cur = 0;
for(int i = 0;i < nums.length;++i){
cur +=nums[i];
//cur先加了，然后就是需要减一个多的中心索引值
if(2*cur-nums[i] == sum) return i;
}
return -1;
}
//执行用时: 1 ms
//内存消耗: 39.2 MB
解法一：(初识解法)
给定一个 排序数组 和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中， 返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。
public int searchInsert(int[] nums, int target) {
int num = 0;
//目标值存在
for(int i = 0;i < nums.length;i++){
if(nums[i] == target){
num = i;
}
}
//目标值不存在，寻找应该插入的位置
if(num == 0){
for(int i = 0;i<nums.length;i++){
if(i == 0){
if(target < nums[i]){
num = 0;
}
}
if(i >=0 && i< nums.length-1){
if(target > nums[i] && target < nums[i+1]){
num = i+1;
}
}else{
if(target > nums[i]){
num = i+1;
}
}
}
}
return num;
}
//执行用时: 1 ms
//内存消耗: 37.9 MB
解法二：暴力解法
public int searchInsert(int[] nums, int target) {
for(int i = 0; i < nums.length;i++){
if(nums[i] >= target){
return i;
}
}
return nums.length;
//执行用时: 0 ms
//内存消耗: 38 MB
解法三：二分法（题目给的是有序数组，无重复元素）
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left <= right){
int mid = left + ((right-left)/2); //防止溢出
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
right = mid - 1;
} else if(nums[mid] < target){
left = mid + 1;
}
}
return right +1;
}
总结：二分法查找的常用格式
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = mid = left + (right - left) / 2;
//等同于mid = (right + left) / 2，但是上面的写法可以防止溢出！！！
//先记住防溢出写法！
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
注意： . . . 标记的部分是需要注意的细节问题
分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。
二分查找算法的一个简单举例：寻找一个有序数组中的元素，有返回该数索引，没有就返回-1；
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length -1;
while(left <= right){
int mid = left + ((right-left)/2); //防止溢出
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid +1;
}else if(nums[mid] > target){
rigth = mid -1;
}
}
return -1;
}