724. 寻找数组的中心下标

题目

自己写的

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> s(n, 0);
        s[0] = nums[0];
        for (int i = 1; i != n; ++i)
            s[i] = s[i - 1] + nums[i];
        for (int i = 0; i != n; ++i)
            if (s[i] - nums[i] == s[n - 1] - s[i])
                return i;
        return -1;
    }
};

看到这题第一眼，就觉得要用区间和来做。

看了卡哥思路，原来也可以不用区间和来做，而且似乎这个方案更优于区间和。

卡哥思路：

卡哥代码：

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = 0;
        for (int num : nums) sum += num; // 求和
        int leftSum = 0;    // 中心索引左半和
        int rightSum = 0;   // 中心索引右半和
        for (int i = 0; i < nums.size(); i++) {
            leftSum += nums[i];
            rightSum = sum - leftSum + nums[i];
            if (leftSum == rightSum) return i;
        }
        return -1;
    }
};

而且卡哥这个代码里面还有一个妙处是在对nums[i]的处理上，让左右两边都加上nums[i]，都加上一个相同的数，是不影响左右两边大小的判断的，而且通过这一举动，让代码也似乎简洁了些。

官方代码也蛮好的，先用数学思维化简了以下该题目：

官方思路：

官方代码：

class Solution {
public:
    int pivotIndex(vector<int> &nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }
};

补充一下accumulate函数

在 C++ 中，accumulate 是 <numeric> 头文件中提供的一个函数，用于对容器中的元素进行累计操作。它可以计算元素的总和，或者根据用户提供的操作函数累积计算结果。

语法：

#include <numeric>
template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);

template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);

参数说明

• first 和 last：输入迭代器，指定范围 [first, last)。

• init：初始值，用于累加的起点。

• binary_op (可选)：一个二元操作函数或仿函数，指定累积时使用的自定义操作。

返回值

• 返回累积操作后的结果。

使用示例

• 示例 1：计算总和

  #include <iostream>
  #include <numeric>
  #include <vector>
  
  int main() {
      std::vector<int> nums = {1, 2, 3, 4, 5};
      int sum = std::accumulate(nums.begin(), nums.end(), 0); // 初始值为0
      std::cout << "Sum: " << sum << std::endl; // 输出: Sum: 15
      return 0;
  }
  

• 示例 2：计算累积

  #include <iostream>
  #include <numeric>
  #include <vector>
  
  int main() {
      std::vector<int> nums = {1, 2, 3, 4};
      int product = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<int>()); // 初始值为1
      std::cout << "Product: " << product << std::endl; // 输出: Product: 24
      return 0;
  }
  

• 示例 3：字符串拼接

  #include <iostream>
  #include <numeric>
  #include <vector>
  #include <string>
  
  int main() {
      std::vector<std::string> words = {"Hello", " ", "World", "!"};
      std::string result = std::accumulate(words.begin(), words.end(), std::string("")); // 初始值为空字符串
      std::cout << "Concatenated string: " << result << std::endl; // 输出: Concatenated string: Hello World!
      return 0;
  }
  

• 示例 4：自定义累计规则

  1. 需求：计算所有数字的平方和

     #include <iostream>
     #include <numeric>
     #include <vector>
     
     int main() {
         std::vector<int> nums = {1, 2, 3, 4};
         // 自定义规则：累加平方值
         int squareSum = std::accumulate(nums.begin(), nums.end(), 0, 
                                         [](int acc, int x) { return acc + x * x; });
         std::cout << "Sum of squares: " << squareSum << std::endl; // 输出: Sum of squares: 30
         return 0;
     }
     

     解释

     • [](int acc, int x)：这是一个 Lambda 表达式，表示累积时将每个元素的平方加到累计结果中。

     • 初始值为 0，然后逐步将每个元素平方后的值累加到 acc 中。

  2. 需求：找到最长字符串的长度

     #include <iostream>
     #include <numeric>
     #include <vector>
     #include <string>
     
     int main() {
         std::vector<std::string> words = {"C++", "Programming", "Language"};
         // 自定义规则：找最长字符串长度
         int maxLength = std::accumulate(words.begin(), words.end(), 0, 
                                         [](int maxLen, const std::string& word) { 
                                             return std::max(maxLen, static_cast<int>(word.length())); 
                                         });
         std::cout << "Longest word length: " << maxLength << std::endl; // 输出: Longest word length: 11
         return 0;
     }
     

注意

• 初始值的类型 T 会影响结果类型。例如，如果初始值是浮点类型，结果也会是浮点类型。

• 使用自定义操作时，确保二元操作符满足累积逻辑。

通过 accumulate，可以方便地对容器进行灵活的累计操作，减少手动循环的代码量。