发表于 2024.08.30

• 枚举右维护左的做法(有点像前缀和)，使用digits数组维护当前位置左边所有数字各个位中的数字出现次数，具体而言，digits[i][j]表示左侧所有数字中，第i位数字为j的个数。遍历数组nums，对于每个数字，遍历每一位，统计左侧所有数字中，不同于当前数字该位的数字出现次数，累加到答案中。

  C++的做法：

  class Solution {
  public:
      using ll = long long;
      long long sumDigitDifferences(vector<int>& nums) {
          // digits[i][j]表示左侧所有数字中，第i位数字为j的个数
          vector<vector<ll>> digits(10, vector<ll>(10));
          ll ans = 0;
          for (int i = 0; i < nums.size(); ++i) {
              int num = nums[i];
              int idx = 0;
              while (num) {
                  int digit = num % 10;
  
                  for (int k = 0; k < 10; ++k) {
                      if (k == digit) continue;  // 与当前数字该位的数字相同的不算
                      ans += digits[idx][k];  // 累加左侧所有数字中，第idx位不同于当前数字该位的数字出现次数
                  }
  
                  ++digits[idx][digit];  // 更新digits数组
                  ++idx; num /= 10;
              }
          }
          return ans;
      }
  };

• LC 题目链接