两数组元素最大和、最大差值索引求解：现有解法是否正确？有无更优方案？

现有两个整数数组：

var arrayA = new int[] { 1, -2, 3, 4, 15, 7, 9, 2 };
var arrayB = new int[] { 6, 7, 8, 9, 10, 12, 11 };

需求：找出两数组元素相加结果最大的元素索引，以及两数组元素相减（取绝对值最大）结果最大的元素索引。

期望输出：

SUM: value: 27, index of A: 4, index of B: 5
SUBTRACT: value: 14, index of A: 1, index of B: 5

我采用双重循环的方式实现了该需求，代码如下：

int SUM=-1000;
int IndexA = 0;
int IndexB = 0;
for (int i = 0; i < arrayA.Count(); i++)
    for (int j = 0; j < arrayB.Count(); j++)
    { 
        if(arrayA[i]+ arrayB[j] > SUM)
        {
             SUM = arrayA[i] + arrayB[j];
             IndexA = i;
             IndexB = j;
        }
            
    }
Console.WriteLine("SUM: value: " + SUM.ToString() + ", index of A: " + 
                 IndexA.ToString() + ", index of B: " + IndexB.ToString());


int SUBTRACT = -1000;
int _IndexA = 0;
int _IndexB = 0;
for (int i = 0; i < arrayA.Count(); i++)
   for (int j = 0; j < arrayB.Count(); j++)
   {
       if (arrayA[i] - arrayB[j] > SUBTRACT)
       {
            SUBTRACT = arrayA[i] - arrayB[j];
            _IndexA = i;
            _IndexB = j;
       }

       if ( arrayB[j] - arrayA[i] > SUBTRACT)
       {
             SUBTRACT = arrayB[j] - arrayA[i];
             _IndexA = i;
             _IndexB = j;
       }

   }
Console.WriteLine("SUBTRACT: value: " + SUBTRACT.ToString() + ", index of A: " + _IndexA.ToString() + ", index of B: " + _IndexB.ToString());

请问该解法是否正确？是否存在更优的实现方式？

一、解法正确性判断 #

你的代码是正确的，可以得到符合期望的输出：

• 相加最大值：arrayA[4]（15） + arrayB[5]（12）=27，对应索引正确；
• 绝对值相减最大值：|arrayA[1]（-2） - arrayB[5]（12）|=14，对应索引正确。

不过有个细节需要优化：初始化的SUM=-1000和SUBTRACT=-1000存在极端场景漏洞。如果数组全是极小负数，相加/绝对值相减结果可能比-1000更小，此时初始值会导致错误判断。建议用int.MinValue作为初始值，覆盖所有整数范围的情况。

二、更优实现方式 #

双重循环的时间复杂度是O(n*m)（n为arrayA长度，m为arrayB长度），数组规模较大时效率偏低。可以通过数学规律将时间复杂度优化到O(n+m)：

1. 相加最大值的最优逻辑 #

两个数相加的最大值，必然是arrayA的最大值加上arrayB的最大值。只需：

• 遍历arrayA找到最大值及其索引；
• 遍历arrayB找到最大值及其索引；
• 两者的和就是最大相加值，对应索引即为结果。

2. 绝对值相减最大值的最优逻辑 #

绝对值|a - b|的最大值只会出现在两种情况：

• arrayA的最大值减去arrayB的最小值；
• arrayB的最大值减去arrayA的最小值；
  取这两个结果中的较大者，对应的索引就是目标结果。

优化后的代码示例 #

// 处理相加最大值
(int maxA, int idxA) = GetMaxWithIndex(arrayA);
(int maxB, int idxB) = GetMaxWithIndex(arrayB);
int maxSum = maxA + maxB;
Console.WriteLine($"SUM: value: {maxSum}, index of A: {idxA}, index of B: {idxB}");

// 处理绝对值相减最大值
(int minA, int minIdxA) = GetMinWithIndex(arrayA);
(int minB, int minIdxB) = GetMinWithIndex(arrayB);
int diff1 = maxA - minB;
int diff2 = maxB - minA;
int maxAbsSub;
int subIdxA, subIdxB;

if (diff1 > diff2)
{
    maxAbsSub = diff1;
    subIdxA = idxA;
    subIdxB = minIdxB;
}
else
{
    maxAbsSub = diff2;
    subIdxA = minIdxA;
    subIdxB = idxB;
}
Console.WriteLine($"SUBTRACT: value: {maxAbsSub}, index of A: {subIdxA}, index of B: {subIdxB}");

// 辅助方法：获取数组最大值及其索引
static (int Value, int Index) GetMaxWithIndex(int[] arr)
{
    int max = arr[0];
    int index = 0;
    for (int i = 1; i < arr.Length; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
            index = i;
        }
    }
    return (max, index);
}

// 辅助方法：获取数组最小值及其索引
static (int Value, int Index) GetMinWithIndex(int[] arr)
{
    int min = arr[0];
    int index = 0;
    for (int i = 1; i < arr.Length; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
            index = i;
        }
    }
    return (min, index);
}

优化效果说明 #

• 时间复杂度从O(n*m)降至O(n+m)，数组规模越大，性能提升越显著；
• 代码逻辑更清晰，避免了嵌套循环的冗余计算；
• 同样能准确输出期望结果，且覆盖了所有整数场景。

内容的提问来源于stack exchange，提问作者user20369604