LC寻找数组的中心索引

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

寻找数组的中心索引

题目链接

给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。

我们是这样定义数组 中心索引 的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

示例1:

输入：

nums = [1,7,3,6,5,6] ### 输出： 3
解释：

索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11)，与右侧数之和 (5 + 6 = 11) 相等。 同时, 3 也是第一个符合要求的中心索引。

示例2:

输入：

nums = [1,2,3]

输出：-1

解释：

数组中不存在满足此条件的中心索引

说明：

  • nums 的长度范围为【0，10000】。
  • 任何一个nums[i]将会是一个范围在[-1000，1000]的整数。

思路

第一种思路是我们定义leftsum 和 rightsum,分别从两头加，直到leftsum == rightsum且它们之间还有一个元素。

第二种思路就是我们可以知道totalSum = leftsum + rightsum + mums[i]

leftsum == rightsum,

所以 2*leftsum = totalSum - nums[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
    	if(nums.size() == 0) return -1;
    	int sum = 0, leftsum = 0;
    	for(int i=0;i<nums.size();i++){
    		sum += nums[i];
    	}
    	for (int i=0;i<nums.size();i++){
    		if(leftsum * 2 == sum - nums[i]) return i;
    		else leftsum += nums[i];
    	}
    	return -1;
    }
};

总的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

/*
思路：
leftsum + rightsum + nums[i] = sum
leftsum*2 = sum -nums[i]
*/
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
    	if(nums.size() == 0) return -1;
    	int sum = 0, leftsum = 0;
    	for(int i=0;i<nums.size();i++){
    		sum += nums[i];
    	}
    	for (int i=0;i<nums.size();i++){
    		if(leftsum * 2 == sum - nums[i]) return i;
    		else leftsum += nums[i];
    	}
    	return -1;
    }
};

int main(){
	int arr[6]={1,7,3,6,5,6};
	vector<int> nums(arr,*(arr +1));
	Solution a;
	int b;
	b = a.pivotIndex(nums);
	cout << b << endl;
	return 0;
}